Problem:


Score : 500 points

Problem Statement

There is an infinitely long street that runs west to east, which we consider as a number line.

There are N roadworks scheduled on this street.
The i-th roadwork blocks the point at coordinate X_i from time S_i - 0.5 to time T_i - 0.5.

Q people are standing at coordinate 0. The i-th person will start the coordinate 0 at time D_i, continue to walk with speed 1 in the positive direction and stop walking when reaching a blocked point.

Find the distance each of the Q people will walk.

Constraints

All values in input are integers.

1 \leq N, Q \leq 2 \times 10^5

0 \leq S_i < T_i \leq 10^9

1 \leq X_i \leq 10^9

0 \leq D_1 < D_2 < ... < D_Q \leq 10^9

If i \neq j and X_i = X_j, the intervals [S_i, T_i) and [S_j, T_j) do not overlap.

Input

Input is given from Standard Input in the following format:

N Q
S_1 T_1 X_1
:
S_N T_N X_N
D_1
:
D_Q

Output

Print Q lines. The i-th line should contain the distance the i-th person will walk or -1 if that person walks forever.

Sample Input 1

4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8

Sample Output 1

2
2
10
-1
13
-1

The first person starts coordinate 0 at time 0 and stops walking at coordinate 2 when reaching a point blocked by the first roadwork at time 2.

The second person starts coordinate 0 at time 1 and reaches coordinate 2 at time 3. The first roadwork has ended, but the fourth roadwork has begun, so this person also stops walking at coordinate 2.

The fourth and sixth persons encounter no roadworks while walking, so they walk forever. The output for these cases is -1.



Sample input:
4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8


Sample output:
2
2
10
-1
13
-1

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, Q = map(int, input().split())

constructions = []
for _ in range(N):
    s, t, x = map(int, input().split())
    heapq.heappush(constructions, (x, s-x, t-x))

max_d = 0
D = []
for i in range(Q):
    d = int(input())
    heapq.heappush(D, (d, i))
    max_d = max(max_d, d)

distance = [-1 for _ in range(Q)]
while constructions:
    x, s, t = heapq.heappop(constructions)
    if max_d < s:
        continue
    new_D = []
    while D:
        d, idx = heapq.heappop(D)
        if d >= s and d < t:
            distance[idx] = x
        else:
            new_D.append((d, idx))
            if d >= t:
                break
    D += new_D
    heapq.heapify(D)
for d in distance:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,Q = (int(x) for x in input().split())

stop_arr = [(0,0,0) for _ in range(N)]
for i in range(N):
    S,T,X = (int(x) for x in input().split())
    stop_arr[i] = (S,T,X)
Q_arr = [0 for _ in range(Q)]
for i in range(Q):
    Q_arr[i] = int(input())

stop_arr.sort(key=lambda x:x[2], reverse=True)

ans_arr = [-1]*Q

for s,t,x in stop_arr:
    q_start = bisect.bisect_left(Q_arr, s-x)
    q_stop = bisect.bisect_left(Q_arr, t-x)
    for i in range(q_start, q_stop):
        ans_arr[i] = x

for a in ans_arr:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
from collections import Counter

N, Q = map(int, input().split(" "))
check_points = [list(map(int, input().split(" "))) for _ in range(N)]
querys = sorted([int(input()) for i in range(Q)])


time = Counter()

check_parsed = []
for s, f, x in sorted(check_points, key=itemgetter(2)):
    start, end = [max(0, s-x), max(0, f-x)]
    for q in querys:
        if q < start:
            pass
        elif start <= q < end:
            if time[q] == 0:
                time[q] = x+1
            else:
                pass
        else:
            break

for q in querys:
    print(time[q]-1)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
kouzi = []
for i in range(N):
    s,t,x = map(int,input().split())
    kouzi.append([s,t,x])
kouzi = sorted(kouzi, key=lambda x:(x[2]))
for j in range(Q):
    d = int(input())
    hehen = [( i[0]-d, i[1]-d , i[2] ) for i in kouzi]
    kotae = -1
    for k in hehen:
        if k[0] <= k[2] and k[1] > k[2]:
            kotae = k[2]
            break
    print(kotae)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())

d = {}
for _ in range(N):
    S,T,X = map(int,input().split())
    for x in range(max(0,S-X),max(0,T-X)):
        if x in d.keys():
            d[x] = min(d[x],X)
        else:
            d[x] = X

for _ in range(Q):
    D = int(input())
    if D in d.keys():
        print(d[D])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n, q = map(int, input().split())
c = []
for _ in range(n):
  s, t, x = map(int, input().split())
  c.append((s, t, x))
c_sorted = sorted(c, key=lambda z: z[2], reverse=True)

d = [-1000000001] + [None] * q + [1000000001]
for i in range(q):
  d[i+1] = int(input())
ans = [-1] * (q+2)
  
for z in c_sorted:
  s = bisect.bisect_left(d, z[0]-z[2])
  l = bisect.bisect_left(d, z[1]-z[2])
#  print(s, l)
  for i in range(s, l):
    ans[i] = z[2]

for i in range(1, q+1):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
stops = [list(map(int, input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]
INF = 10**9
res = [INF for i in range(max(D)+1)]

for stop in stops:
    d = stop[2]
    r = [i-d for i in range(stop[0], stop[1]) if i - d >= 0]
    for i in r:
        if i > max(D):
            break
        if res[i] > d:
            res[i] = d

for i in range(len(res)):
    if res[i] == INF:
        res[i] = -1

for d in D:
    print(res[d])

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
STX = [list(map(int,input().split())) for _ in [0]*N]
D = [int(input()) for _ in [0]*Q] + [10**10]
STX.sort(key=lambda x:(-x[2],x[0]))

def binary_search(n):
    if n<D[0]:return 0
    l=0
    r=Q+1
    while l+1<r:
        i = (l+r)//2
        if D[i]<n:l=i
        else: r=i
    return r

ans = [-1]*(Q+1)
for s,t,x in STX:
    sd = s-x-0.5
    td = t-x-0.5
    l = binary_search(sd)
    r = binary_search(td)
    ans[l:r] = [x]*(r-l)
for o in ans[:-1]:
    print(o)

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
kouji=[tuple(map(int,input().split())) for i in range(N)]
D=[int(input()) for i in range(Q)]
kouji_kai=[(max(0,S-X),T-X-1,X) for S,T,X in kouji]
kouji_kai.sort(key=lambda x:x[2])
for d in D:
    ans=-1
    for b,e,x in kouji_kai:
        if b<=d<=e:
            ans=x
            break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def f(n, q):
    stx = []
    for i in range(n):
        s, t, x = map(int, input().split())
        stx.append([s - x, t - x, x])
    stx.sort(key=lambda x: x[2])
    ds = []
    for i in range(q):
        d = int(input())
        for s, t, x in stx:
            if s <= d < t:
                print(x)
                break
        else:
            print(-1)

n, q = map(int, input().split())
f(n, q)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,Q=map(int,input().split())
A=np.zeros(N, dtype=np.int32)
B=np.zeros(N, dtype=np.int32)
X=np.zeros(N, dtype=np.int32)
T=np.zeros(N, dtype=np.int32)
inf=10**9+1
for i in range(N):
	a,b,x=map(int,input().split())
	A[i]=a
	B[i]=b
	X[i]=x
for i in range(Q):
	D = np.ones(N)*int(input())
	E = (A-X)<=D
	F = D<=(B-X-1)
	G = E*F
	if np.sum(G)==0:
		print(-1)
	else:
		T=np.where(G,X+D,inf)
		id=np.argmin(T)
		print(X[id])

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
sl=[list(map(int,input().split())) for i in range(n)]
s=set()
d=dict()
for i in range(n):
    for j in range(max(sl[i][0]-sl[i][2],0),sl[i][1]-sl[i][2]):
        if j not in s:
            d[j]=sl[i][2]
            s.add(j)
        else:
            d[j]=min(sl[i][2],d[j])

for i in range(q):
    x=int(input())
    print(-1 if x not in s else d[x])

Submission status: Time Limit Exceeded

Solution code:
N,Q=(int(x) for x in input().split())
L=[]
for _ in range(N):
    S,T,X=(int(x) for x in input().split())
    L.append([S-X,T-X-1,X])#Xで引っ掛かる人で最も早いスタート,最も遅いスタート,X

L.sort(key=lambda elm:elm[2])#Xの小さい順に並び変え


for _ in range(Q):
    D=int(input())
    bol=True
    for s,t,x in L:
        if s<=D and D<=t:
            print(x)
            bol=False
            break
    if bol:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
N, Q=map(int, input().split())
stx=list(sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x : x[2]))
D=[int(input()) for _ in range(Q)]
for j in range(Q):
    flag=0
    for i in range(N):
        if stx[i][1]<=D[j]:
            continue
        if stx[i][0]<=stx[i][2]+D[j]<=stx[i][1]-1:
            print(stx[i][2])
            flag=1
            break
    if flag==0:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

N, Q = map(int, input().split())
SmXTmXX = []
for _ in range(N):
    s, t, x = map(int, input().split())
    SmXTmXX.append((s - x, t - x, x))
DI = []
D = []
for i in range(Q):
    d = int(input())
    D.append(d)

ans = [-1] * Q
for n in range(N):
    di, dj, x = SmXTmXX[n]
    i = bisect_left(D, di)
    j = bisect_left(D, dj, i)
    for k in range(i, j):
        ans[k] = x if ans[k] == -1 else min(ans[k], x)
for v in ans:
    print(v)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from functools import *
from itertools import *
import operator as op

def main():
    #n = int(input())
    n, q = map(int, input().split())
    #xs = list(map(int, input().split()))
    #xs = [ input().split() for _ in range(n) ]
    xs = [ list(map(int, input().split())) for _ in range(n) ]
    xs.sort(key=lambda x: x[2])
    ds = [ int(input()) for _ in range(q) ]

    ys = [ (max(0, s-x), t-x, x) for s, t, x in xs if t-x >= 0]

    def doit(xs, d):
        for s, t, x in ys:
            if d >= s and d < t:
                return x
            pass
        return -1

    for d in ds:
        print(doit(xs, d))
        pass

    pass


if __name__ == "__main__":
    main()
    pass

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import bisect

n, q = [int(_) for _ in input().split()]

rs = []
for i in range(n):
    s, t, x = [int(_) for _ in input().split()]
    rs.append((s - x, x))
    rs.append((t - x, ~x))

rs.sort()
dks = []
dvs = []
sts = set()
msts = -1
prev_i = None
for i, x in rs:
    if x < 0:
        sts.remove(~x)
        msts = msts if msts != ~x else min(sts) if sts else -1
    else:
        sts.add(x)
        msts = x if msts == -1 else min(msts, x)
    if prev_i == x:
        del dvs[-1]
    else:
        dks.append(i)
    dvs.append(msts)
    prev_i = i


for _ in range(q):
    d = int(input())
    i = bisect.bisect(dks, d) - 1
    if 0 <= i < len(dks) - 1 and dks[i] <= d < dks[i + 1]:
        print(dvs[i])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,Q=map(int,input().split())
A=np.zeros(N, dtype=np.int32)
B=np.zeros(N, dtype=np.int32)
X=np.zeros(N, dtype=np.int32)
T=np.zeros(N, dtype=np.int32)
inf=10**9+1
for i in range(N):
	a,b,x=map(int,input().split())
	A[i]=a
	B[i]=b
	X[i]=x
for i in range(Q):
	D = np.ones(N)*int(input())
	E = (A-X)<=D
	F = D<=(B-X-1)
	#print(E*F)
	if np.sum(E*F)==0:
		print(-1)
	else:
		T=np.where(E*F,X+D,inf).astype(np.int32)
		#print(T)
		id=np.argmin(T)
		print(X[id])

Submission status: Time Limit Exceeded

Solution code:
import numpy
import bisect
N,Q = (int(x) for x in input().split())

stop_arr = []
for _ in range(N):
    S,T,X = (int(x) for x in input().split())
    stop_arr.append((S,T,X))
Q_arr = []
for _ in range(Q):
    Q_arr.append(int(input()))

stop_arr.sort(key=lambda x:x[2], reverse=True)

Q_arr = numpy.array(Q_arr)
ans_arr = numpy.array([-1]*Q)

for s,t,x in stop_arr:
    q_start = numpy.searchsorted(Q_arr, s-x)
    q_stop = numpy.searchsorted(Q_arr, t-x)
    ans_arr[q_start:q_stop] = x

for a in ans_arr:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
stx=[]
for i in range(n):
    s,t,x=map(int,input().split())
    stx.append([s-x,t-x,x])
stx.sort(key=lambda x:x[2])
ds=[]
for i in range(q):
    d=int(input())
    for s,t,x in stx:
        if s<=d<t:
            print(x)
            break
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n, q = map(int, input().split())
c = []
for _ in range(n):
  s, t, x = map(int, input().split())
  c.append((s, t, x))
c_sorted = sorted(c, key=lambda z: z[2], reverse=True)

d = [-1000000001]
for _ in range(q):
  i = int(input())
  d.append(i)
d.append(1000000001)
ans = [-1 for _ in range(q+2)]
  
for z in c_sorted:
  s = bisect.bisect_left(d, z[0]-z[2])
  l = bisect.bisect_left(d, z[1]-z[2])
#  print(s, l)
  for i in range(s, l):
    ans[i] = z[2]

for i in range(1, q+1):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import numpy
import bisect
N,Q = (int(x) for x in input().split())

stop_arr = []
for _ in range(N):
    S,T,X = (int(x) for x in input().split())
    stop_arr.append((S,T,X))
Q_arr = []
for _ in range(Q):
    Q_arr.append(int(input()))

stop_arr.sort(key=lambda x:x[2], reverse=True)

Q_arr = numpy.array(Q_arr)
ans_arr = numpy.array([-1]*Q)

for s,t,x in stop_arr:
    q_start = numpy.searchsorted(Q_arr, s-x)
    q_stop = numpy.searchsorted(Q_arr, t-x)
    ans_arr[q_start:q_stop].fill(x)

for a in ans_arr:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections
import operator

N, Q = map(int, sys.stdin.readline().rstrip().split(" "))
stops = []
for _ in range(N):
    S, T, X = map(int, sys.stdin.readline().rstrip().split(" "))
    stops.append((S, T, X))
stops.sort(key=operator.itemgetter(2))

for _ in range(Q):
    D, = map(int, sys.stdin.readline().rstrip().split(" "))
    for S, T, X in stops:
        if S <= D + X and D + X <= (T - 1):
            print(X)
            break
    else:
        print(-1)

exit(0)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
kouzi = []
for i in range(N):
    s,t,x = map(int,input().split())
    kouzi.append([s,t,x])

for j in range(Q):
    d = int(input())
    hehen = [( (i[0]-d)/i[2], (i[1]-d)/i[2] , i[2] ) for i in kouzi]
    hehen = sorted(hehen, key=lambda x:(x[2]))
    kotae = -1
    for k in hehen:
        if k[0] <= 1 and k[1] > 1:
            kotae = k[2]
            break
    print(kotae)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S, T, X = [0] * N, [0] * N, [0] * N
for i in range(N):
	S[i], T[i], X[i] = map(int, input().split())
D = [[int(input()), float("inf")] for _ in range(Q)]

for j in range(Q):
	for k in range(N):
		if S[k] - X[k] <= D[j][0] < T[k] - X[k]:
			D[j][1] = min(D[j][1], X[k])

for l in range(Q):
	if D[l][1] == float("inf"):
		print(-1)
	else:
		print(D[l][1])

Submission status: Time Limit Exceeded

Solution code:
N, Q=map(int, input().split())
stx=list(sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x : x[2]))
D=[int(input()) for _ in range(Q)]
for j in range(Q):
    flag=0
    for i in range(N):
        if stx[i][0]<=stx[i][2]+D[j]<=stx[i][1]-1:
            print(stx[i][2])
            flag=1
            break
    if flag==0:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from functools import *
from itertools import *
import operator as op

def main():
    #n = int(input())
    n, q = map(int, input().split())
    #xs = list(map(int, input().split()))
    #xs = [ input().split() for _ in range(n) ]
    xs = [ list(map(int, input().split())) for _ in range(n) ]
    xs.sort(key=lambda x: x[2])
    ds = [ int(input()) for _ in range(q) ]

    def doit(xs, d):
        for s, t, x in xs:
            u = d + x
            if u >= s and u < t:
                return x
            pass
        return -1

    for d in ds:
        print(doit(xs, d))
        pass

    pass


if __name__ == "__main__":
    main()
    pass

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(n)]
p.sort(key=lambda x: x[2])
d = [int(input()) for _ in range(q)]
ans = [-1] * q
for i, di in enumerate(d):
    for j in range(n):
        s, t, x = p[j]
        tj = x + di
        if s <= tj < t:
            ans[i] = x
            break
for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
n, q = list(map(int, input().split()))
ks = []
for _ in range(n):
    s, t, x = list(map(int, input().split()))
    ks.append((s, t, x))

ds = dict()
ks = sorted(ks, key=lambda k: k[2], reverse=True)
for k in ks:
    s, t, x = k
    for tt in range(s - x, t - x):
        ds[tt] = x


for _ in range(q):
    d = int(input())
    if d in ds:
        print(ds[d])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import copy
from heapq import heappush, heappop
n, q = map(int, input().split())
heap = []
for i in range(n):
  s, t, x = map(int, input().split())
  heappush(heap, [x, s, t])
for i in range(q):
  d = int(input())
  heap_copy = copy.deepcopy(heap)
  for j in range(n):
    x, s, t = heappop(heap_copy)
    if s - 0.5 < d + x and d + x < t - 0.5:
      print(x)
      break
  else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,Q = (int(x) for x in input().split())

stop_arr = []
for _ in range(N):
    S,T,X = (int(x) for x in input().split())
    stop_arr.append((S,T,X))
Q_arr = []
for _ in range(Q):
    Q_arr.append(int(input()))

stop_arr.sort(key=lambda x:x[2], reverse=True)

ans_arr = [-1]*Q

for s,t,x in stop_arr:
    q_start = bisect.bisect_left(Q_arr, s-x)
    q_stop = bisect.bisect_left(Q_arr, t-x)
    for i in range(q_start, q_stop):
        ans_arr[i] = x

for a in ans_arr:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappush,heappop

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  heappush(q,(s-x,1,x)) # xで死ぬ
  heappush(q,(t-x,0,x)) # xで死ななくなる
  
D = [int(input()) for _ in range(Q)]
for i,d in enumerate(D):
  heappush(q,(d,2,i))
answer = [-1]*Q

se = set() # 引っかかってる場所

while q:
  a,c,b = heappop(q)
  if c == 2: # queryに答える
    if se:
      answer[b] = min(se)
  elif c == 1:
    se.add(b)
  elif c == 0:
    se.remove(b)

    
for x in answer:
  print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline

n,q = map(int,input().split())
x = []
for i in range(n):
        x.append(list(map(int,input().split())))
x.sort(key = lambda x : x[2])
dd = []
zaa = []
for i in range(q):
        a = int(input())
        dd.append(a)
        zaa.append(a)
y = []

for i in range(n):
        a = x[i][0]-x[i][2]
        b = x[i][1]-1-x[i][2]
        y.append([a,b])
        zaa.append(a)
        zaa.append(b)

import bisect
def press(a):
    n = len(a)
    b = set(a)
    b = list(b)
    b.sort()
    c = [0] * n
    for i in range(n):
        c[i] = bisect.bisect_left(b,a[i])
    return b,c
zaa.sort()
mo,za = press(zaa)
mo = zaa
d = dict()
for i in range(len(zaa)):
        d[mo[i]] = za[i]+1
dg = dict()
for i in range(len(zaa)):
        dg[za[i]+1] = mo[i]



INF = 2**38-1

LV = (len(set(za))+1).bit_length()
N0 = 2**LV
data = [INF]*(2*N0)
lazy = [None]*(2*N0)

# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

# 区間[l, r)をxで更新
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
for i in range(n-1,-1,-1):
        update(d[y[i][0]], d[y[i][1]]+1, i+1)
for i in range(q):
        ans = query(d[dd[i]],d[dd[i]]+1)
        if ans == INF:
                print(-1)
        else:
                print(x[ans-1][2])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
STX = [list(map(int, input().split())) for n in range(N)]
D = [int(input()) for q in range(Q)]

max_X = max(map(lambda x: x[2], STX))
max_T = max(map(lambda x: x[1], STX))

prog = []
finish = [-1] * Q
next_D = 0
for i in range(max_T + 1):
    now = [l[2] for l in filter(lambda r: r[0] <= i < r[1], STX)]
    remove = []
    for p in prog:
        p[1]+=1
        if p[1] in now:
            finish[p[0]] = p[1]
            remove.append(p)
        elif p[1] == max_X:
            finish[p[0]] = -1
            remove.append(p)            
    for p in remove:
        prog.remove(p)
    if next_D != -1 and i == D[next_D]:
        prog.append([next_D, 0])
        next_D = next_D + 1 if next_D < Q-1 else -1
for f in finish:
    print(f)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
#input = sys.stdin.readline

n,q = map(int,input().split())
x = []
for i in range(n):
        x.append(list(map(int,input().split())))
x.sort(key = lambda x : x[2])
dd = []
zaa = []
for i in range(q):
        a = int(input())
        dd.append(a)
        zaa.append(a)
y = []

for i in range(n):
        a = x[i][0]-x[i][2]
        b = x[i][1]-1-x[i][2]
        y.append([a,b])
        zaa.append(a)
        zaa.append(b)

import bisect
def press(a):
    n = len(a)
    b = set(a)
    b = list(b)
    b.sort()
    c = [0] * n
    for i in range(n):
        c[i] = bisect.bisect_left(b,a[i])
    return b,c
zaa.sort()
mo,za = press(zaa)
mo = zaa
d = dict()
for i in range(len(zaa)):
        d[mo[i]] = za[i]+1
dg = dict()
for i in range(len(zaa)):
        dg[za[i]+1] = mo[i]



INF = 2**38-1

LV = (len(set(za))+1).bit_length()
N0 = 2**LV
data = [INF]*(2*N0)
lazy = [None]*(2*N0)

# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

# 区間[l, r)をxで更新
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
for i in range(n-1,-1,-1):
        update(d[y[i][0]], d[y[i][1]]+1, i+1)
for i in range(q):
        ans = query(d[dd[i]],d[dd[i]]+1)
        if ans == INF:
                print(-1)
        else:
                print(x[ans-1][2])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import bisect

n, q = [int(_) for _ in input().split()]

rs = []
ws = []
for i in range(n):
    s, t, x = [int(_) for _ in input().split()]
    rs.append((s - x, i))
    rs.append((t - x, ~i))
    ws.append(x)

rs.sort()
ds = {}
sts = set()
for i, d in rs:
    if d < 0:
        sts.remove(~d)
    else:
        sts.add(d)
    ds[i] = min(
        (ws[st] for st in sts),
        default=-1)

dks, dvs = zip(*sorted(ds.items()))

for _ in range(q):
    d = int(input())
    i = bisect.bisect(dks, d) - 1
    if 0 <= i < len(dks) - 1 and dks[i] <= d < dks[i + 1]:
        print(dvs[i])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
import math

import array
import bisect
import collections
from collections import Counter, defaultdict
import fractions
import heapq
import re

sys.setrecursionlimit(1000000)


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

def argsort(l, reverse=False):
    return sorted(range(len(l)), key=lambda i: l[i], reverse=reverse)

def argmin(l):
    return l.index(min(l))

def YESNO(ans, yes="YES", no="NO"):
    print([no, yes][ans])

II = lambda: int(input())
MI = lambda: map(int, input().split())
MIL = lambda: list(MI())
MIT = lambda: tuple(MI())
MIS = lambda: input().split()


def main():
    N, Q = MI()
    WS = tuple((MIT() for _ in range(N)))
    D = tuple((II() for _ in range(Q)))

    dist = [float("inf")] * Q

    for S, T, X in WS:
        l = bisect.bisect_left(D, S-X)
        r = bisect.bisect_left(D, T-X)
        for i in range(l, r):
            dist[i] = min(dist[i], X)

    for d in dist:
        print(d if d != float("inf") else -1)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())

lst = []
for i in range(N):
    S, T , X = map(int, input().split())
    lst += [[X, max(0, S-X), max(0, T-X)]]

lst.sort()
#print (lst)

def check(a):
    for j in range(len(lst)):
            if lst[j][1] <= D and D < lst[j][2]:
                return lst[j][0]
            elif j == len(lst) - 1:
                return -1

for i in range(Q):
    D = int(input())
    print (check(D))

Submission status: Time Limit Exceeded

Solution code:

N, Q = map(int, input().split())
S = [0]*N
T = [0]*N
X = [0]*N

D = [0]*Q

for i in range(N):
    S[i], T[i], X[i] = map(int, input().split())
for i in range(Q):
    D[i] = int(input())



ans = [-1]*Q



for i in range(N):
    for j in range(Q):
        if D[j]+X[i] >= S[i] and  D[j]+X[i] < T[i] and (ans[j] > X[i] or ans[j] == -1):
            ans[j] = X[i]
        elif D[j]+X[i] < T[i]:
            continue
        
            
for i in range(Q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
XST, D = [], []
for _ in range(N):
    s, t, x = map(int, input().split())
    XST.append((x, s, t))

for _ in range(Q):
    D.append(int(input()))

XST.sort()

def stop(x, s, t, d):
    arv = d + x
    if s <= arv < t:
        return True
    return False

for d in D:
    go = -1
    for xst in XST:
        if stop(xst[0], xst[1], xst[2], d):
            go = xst[0]
            break
    print(go)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
S = [0]*N
T = [0]*N
X = [0]*N

D = [0]*Q

for i in range(N):
    S[i], T[i], X[i] = map(int, input().split())
for i in range(Q):
    D[i] = int(input())



ans = [-1]*Q



for i in range(N):
    for j in range(Q):
        if D[j]+X[i] >= S[i] and  D[j]+X[i] < T[i] and (ans[j] > X[i] or ans[j] == -1):
            ans[j] = X[i]
            
            
for i in range(Q):
    print(ans[i])