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:
from bisect import bisect_left, bisect_right
def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

def find_lt(a, x):
    'Find rightmost value less than x'
    i = bisect_left(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return a[i-1]
    raise ValueError

def find_gt(a, x):
    'Find leftmost value greater than x'
    i = bisect_right(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

def find_ge(a, x):
    'Find leftmost item greater than or equal to x'
    i = bisect_left(a, x)
    if i != len(a):
        return a[i]
    raise ValueError

n, q = map(int, input().split())
range_dict = {}
lefts = []
rights = []
for nn in range(n):
  s, t, x = map(int, input().split())
  left = s - 0.5 - x
  right = t - 0.5 - x
  lefts.append((left, x, 'left'))
  rights.append((right, x, 'right'))
  range_dict[nn + 1] = (left, right, nn+1, x)

#print(range_dict)

ds = [int(input()) for qq in range(q)]
#for d in ds:
#  out = -1
#  for s,t,i,x in sorted(range_dict.values(), key=lambda x: x[3]):
#    if d >= s and d < t:
#      out = x
#      break
#  print(d, out)
#print(lefts)
#print(rights)
borders = sorted(lefts + rights, key=lambda x: x[0])
#print(borders)
border_dict = {}

cur = []
xs = []
for val, x, lr in borders:
  if lr == 'left':
    cur.append(x)
  elif lr == 'right':
    cur.remove(x)
  if cur:
    border_dict[val] = min(cur)
  else:
    border_dict[val] = -1
#print(border_dict)

borders = sorted(border_dict.keys())
#print(borders)
for d in ds:
  out = -1
  try:
    b = find_le(borders, d)
    out = border_dict[b]
  except ValueError:
    print('error')
    out = -1
  print(out)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import heapq
from operator import itemgetter
from bisect import bisect_right
N, Q = map(int, input().split())
Stop = []
for i in range(N):
    S, T, X = map(int, input().split())
    Stop.append([S - X, X, 0, i])
    Stop.append([T - X, X, 1, i])
Stop.sort(key=itemgetter(0))
q = []
notClosed = [False]*N
A = [(-1, -1)]
for time, pos, lr, idx in Stop:
    if lr==0:
        heapq.heappush(q, (pos, time, idx))
    else:
        notClosed[idx] = True
        while len(q)>0 and notClosed[q[0][2]]:
            aaa = heapq.heappop(q)[2]

    if len(q):
        A.append((time, q[0][0]))
    else:
        A.append((time, -1))
for _ in range(Q):
    D = int(input())
    idx = bisect_right(A, (D, 1<<60))

    print(A[idx-1][1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, Q= map(int,input().split())
const_list = []
start_time_list = []
for _ in range(N):
    const_list.append(list(map(int,input().split())))

const_list = np.array(const_list)
start_time_list = np.array(start_time_list)
start = const_list[:,0] - const_list[:,2]
end = const_list[:,1] - const_list[:,2] - 1

for _ in range(Q):
    q = int(input())
    check = (q-start) * (end-q)
    true_index = np.where(check>=0)
    if len(true_index[0])==0:
        print(-1)
    else:
        stop_pos_list = [const_list[:,2][x] for x in true_index[0]]
        print(min(stop_pos_list))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import bisect

def readInts():
  return [int(s) for s in input().split(" ")]

def main():
  N, Q = readInts()
  conds = [readInts() for _ in range(N)]
  D = [readInts()[0] for _ in range(Q)]

  ans = [-1 for _ in range(Q)]
  for S, T, X in conds:
    left = bisect.bisect_left(D, S - X)
    right = bisect.bisect_left(D, T - X)
    for i in range(left, right):
      if ans[i] < 0:
        ans[i] = X
      else:
        ans[i] = min(ans[i], X)

  for a in ans:
    print(a)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

list=input().split(" ")
n=int(list[0])
q=int(list[1])

koji=[]

for i in range(n):
    list=input().split(" ")
    x=int(list[2])
    s=max(0, int(list[0])-x)
    t=max(0, int(list[1])-x)
    heapq.heappush(koji, [x,s,t])

koji=[heapq.heappop(koji) for i in range(len(koji))]
    
#print(koji)

nagasa=len(koji)

for r in range(q):
    now=int(input())
    switch=1
    step=0
    while switch==1:
        if now<koji[step][1] or now>=koji[step][2]:
            step+=1
            if step==nagasa:
                switch=0
                print(-1)
        else:
            print(koji[step][0])
            switch=0

Submission status: Time Limit Exceeded

Solution code:
import bisect


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 = {}
for q in querys:
    time[q] = -1

check_parsed = []
for s, f, x in check_points:
    start, end = [s-x, f-x]
    left = bisect.bisect_left(querys, start)
    right = bisect.bisect_left(querys, end)
    for q in querys[left:right]:
        if time[q] == -1 or time[q] >= x:
            time[q] = x


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

Submission status: Time Limit Exceeded

Solution code:
# from heapq import *
# N, K = [int(i) for i in input().split()]
# V = [int(i) for i in input().split()]
#
# heap=[]
# for i in range(K):
#     V.pop(0)
#     V.pop(len(V)-1)
#     heappop(heap)
#     heappush(heap, )


N, Q = [int(i) for i in input().split()]
X = [[int(i) for i in input().split()] for i in range(N)]
X.sort(key=lambda x:x[2])
D = [int(input()) for i in range(Q)]
for x in X:
    x[0] -= x[2]
    x[1] -= (x[2] + 1)

for d in D:
    stop = False
    for x in X:
        if stop:
            break
        if d >= x[0] and d <= x[1]:
            stop = True
            print(x[2])
    if not stop:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

fin = sys.stdin.readline

n, q = map(int, fin().split())
stx = [tuple(map(int, fin().split())) for _ in range(n)]
d = [int(fin()) for _ in range(q)]

new_st = [(val[0] - val[2], val[1] - val[2], val[2]) for val in stx]
new_st = sorted(new_st, key=lambda x: x[2])
dist = []

for d_ in d:
    for s, t, x in new_st:
        if s <= d_ < t:
            dist.append(x)
            break
    else:
        dist.append(-1)

print(*dist, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
N, Q = list(map(int, input().split()))
dat=[]
for i in range(N):
  dat.append(list(map(int, input().split())))
for i in range(N):
  dat[i]=[dat[i][2],dat[i][0]-dat[i][2],dat[i][1]-dat[i][2]-1]
dat.sort()

stt=[]
for i in range(Q):
  stt.append(int(input()))

for i in range(Q):
  res=-1
  #print('stt->' + str(stt[i]))
  for j in range(N):
    if (stt[i] >= dat[j][1]) and (stt[i] <= dat[j][2]) :
      res=dat[j][0]
      break
  print(res)

Submission status: Time Limit Exceeded

Solution code:
import bisect

kl, ql = tuple(map(int,input().split()))

ks = []
for ki in range(kl):
    a,b,x = tuple(map(int,input().split()))
    #a..b-1 nioite x ha tuukou dome
    ahx, bhx = a-x, b-x
    ks.append((ahx,bhx,x))

ds = []
for qi in range(ql):
    d = int(input())
    ds.append(d)


notyetKs = sorted(ks, key=lambda k:k[0])
workingKs = []
workingKBs = []

for t in ds:
    while len(notyetKs)>0:
        ahx,bhx,x = notyetKs[0]
        if ahx <= t:
            if t < bhx:
                pos = bisect.bisect_left(workingKBs, bhx)
                workingKs.insert(pos,(ahx,bhx,x))
                workingKBs.insert(pos,bhx)
            notyetKs.pop(0)
        else:
            break
    while len(workingKs)>0:
        ahx,bhx,x = workingKs[0]
        if bhx <= t:
            workingKs.pop(0)
            workingKBs.pop(0)
        else:
            break

    #print(t, notyetKs,workingKs,doneKs)

    if len(workingKs)==0:
        print(-1)
    else:
        print(min(workingKs, key=lambda k:k[2])[2])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

#iの値をxに更新
def update(i,x):
	i += NN - 1
	SegTree[i] = x
	while i>0:
		i = (i-1)//2
		SegTree[i] = process(SegTree[i*2+1],SegTree[i*2+2])

#[A,B)の値, 呼ぶときはquery(a,b,0,0,NN)
def query(a,b,k,l,r):
	if r <= a or b <= l: #完全に含まない
		return INF
	elif a <= l and r <= b : #完全に含む
		return SegTree[k]
	else: #交差する
		vl = query(a,b,k*2+1,l,(l+r)//2)
		vr = query(a,b,k*2+2,(l+r)//2,r)
		return(process(vl,vr))

#x,yが子の時，親に返る値
def process(x,y):
	return min(x,y)


N,Q = inpl()
STX = [inpl() for i in range(N)]
DD = [[-int(input()),1,i] for i in range(Q)]


zaatu = defaultdict(int)
for i,[S,T,X] in enumerate(STX):
    l = X - (T-0.5)
    r = X - (S-0.5)
    DD.append([l,3,X])
    DD.append([r,2,X])
    zaatu[X] = i

DD.sort()

L = len(DD)
NN = 1
while NN < L:
	NN *= 2
SegTree = [INF]*(NN*2-1)

ans = [0]*Q
for k,q,x in DD:
    if q == 1:
        ans[x] = query(0,NN,0,0,NN)
    elif q == 3:
        update(zaatu[x],x)
    elif q == 2:
        update(zaatu[x],INF)

for a in ans:
    if a == INF:
        print(-1)
    else:
        print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import heapq
from operator import itemgetter
from bisect import bisect_right
N, Q = map(int, input().split())
Stop = []
for i in range(N):
    S, T, X = map(int, input().split())
    Stop.append([max(0, S - X), X, 0, i])
    Stop.append([max(0, T - X), X, 1, i])
Stop.sort(key=itemgetter(0, 2))
q = []
notClosed = [False]*N
A = [(-1, -1)]
for time, pos, lr, idx in Stop:
    if lr==0:
        heapq.heappush(q, (pos, time, idx))
    else:
        notClosed[idx] = True
        while len(q)>0 and notClosed[q[0][2]]:
            aaa = heapq.heappop(q)[2]
            #notClosed[aaa]

    if len(q):
        A.append((time, q[0][0]))
    else:
        A.append((time, -1))
assert len(q)==0
for _ in range(Q):
    D = int(input())
    idx = bisect_right(A, (D, 1<<60))

    print(A[idx-1][1])

Submission status: Time Limit Exceeded

Solution code:
N, Q = [int(n) for n in input().split()]
S, T, X = [], [], []
for _ in range(N):
    inp = [int(n) for n in input().split()]
    S.append(inp[0])
    T.append(inp[1] - 1)
    X.append(inp[2])
D = [int(input()) for _ in range(Q)]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        XST.append([x, s, t])
    D = []
    for _ in range(Q):
        D.append(II())
    ts = []
    for x, s, t in XST:
        ts.append(s)
        ts.append(t)
    ts.sort()
    ts.append(INF)
    xs = [INF] * (N * 2 + 1)
    XST.sort(reverse=True)
    for x, s, t in XST:
        s0 = bisect(ts, s)
        t0 = bisect(ts, t)
        for i in range(s0, t0):
            xs[i] = x
    for d in D:
        y = bisect(ts, d)
        y = xs[y]
        if y == INF:
            y = -1
        print(y)
    return

main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
stx = []
for _ in range(N):
    stx.append([int(s) for s in input().split()])
d = [int(input()) for _ in range(Q)]

ans = []
for one in d:
    tmp_ans = []
    for k in stx:
        if k[2]+one<k[1]-0.5 and k[0]-0.5<k[2]+one:
            tmp_ans.append(k[2])
    if len(tmp_ans)>=1:
        ans.append(min(tmp_ans))
    else:
        ans.append(-1)
for an in ans:
  print(an)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

ds = sorted([(int(input()), i) for i in range(q)])

dists = [-1 for _ in range(q)]
dts = sorted(dts, key=lambda dti: dti[2], reverse=True)
for dt in dts:
    s, t, x = dt
    li = bisect.bisect_left(ds, (s, -1))
    ri = bisect.bisect_left(ds, (t, -1))
    for i in range(li, ri):
        dists[ds[i][1]] = x

for di in dists:
    print(di)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import bisect


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 = {}
for q in querys:
    time[q] = 0

check_parsed = []
for s, f, x in sorted(check_points, key=itemgetter(2)):
    start, end = [s-x, f-x]
    left = bisect.bisect_left(querys, start)
    right = bisect.bisect_left(querys, end)
    for q in querys[left:right]:
        if time[q] == 0:
            time[q] = x+1


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, Q= map(int,input().split())
const_list = []
start_time_list = []
for _ in range(N):
    const_list.append(list(map(int,input().split())))

const_list = np.array(const_list)
start_time_list = np.array(start_time_list)
start = const_list[:,0] - const_list[:,2]
end = const_list[:,1] - const_list[:,2] - 1

for _ in range(Q):
    q = int(input())
    check = (q-start) * (end-q)
    true_false = check>=0
    if sum(true_false)==0:
        print(-1)
    else:
        stop_pos_list = const_list[:,2][true_false]
        print(min(stop_pos_list))

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 i in range(l,r):ans[i]=x
for o in ans[:-1]:
    print(o)

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
tmp_D = []
for i in range(Q):
    d = int(input())
    heapq.heappush(tmp_D, (d, i))
    max_d = max(max_d, d)

D = []
while tmp_D:
    D.append(heapq.heappop(tmp_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 = D.pop(0)
        if d >= s and d < t:
            distance[idx] = x
        else:
            new_D.append((d, idx))
            if d >= t:
                break
    new_D += D
    D = new_D
for d in distance:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import bisect

def readInts():
  return [int(s) for s in input().split(" ")]

def main():
  N, Q = readInts()
  conds = [readInts() for _ in range(N)]
  D = [readInts()[0] for _ in range(Q)]
  conds.sort(key=lambda x: x[2]) # sort by X

  ans = [-1 for _ in range(Q)]
  for S, T, X in conds:
    left = bisect.bisect_left(D, S - X)
    right = bisect.bisect_left(D, T - X)
    for i in range(left, right):
      if ans[i] < 0:
        ans[i] = X

  for a in ans:
    print(a)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, Q= map(int,input().split())
const_list = []
start_time_list = []
for _ in range(N):
    const_list.append(list(map(int,input().split())))

const_list = np.array(const_list)
start_time_list = np.array(start_time_list)
start = const_list[:,0] - const_list[:,2]
end = const_list[:,1] - const_list[:,2] - 1

for _ in range(Q):
    q = int(input())
    check = (q-start) * (end-q)
    true_index = np.where(check>=0)
    if len(true_index[0])==0:
        print(-1)
    else:
        stop_pos_list = const_list[:,2][check>=0]
        print(min(stop_pos_list))

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()

import heapq
from operator import itemgetter
from bisect import bisect_right
N, Q = map(int, input().split())
Stop = []
for i in range(N):
    S, T, X = map(int, input().split())
    Stop.append([max(0, S - X), X, 0, i])
    Stop.append([max(0, T - X), X, 1, i])
Stop.sort(key=itemgetter(0, 2))
q = []
notClosed = set()
A = [(-1, -1)]
for time, pos, lr, idx in Stop:
    if lr==0:
        heapq.heappush(q, (pos, time, idx))
    else:
        notClosed.add(idx)
        while len(q)>0 and q[0][2] in notClosed:
            aaa = heapq.heappop(q)[2]
            notClosed.remove(aaa)

    if len(q):
        A.append((time, q[0][0]))
    else:
        A.append((time, -1))
assert len(q)==0
for _ in range(Q):
    D = int(input())
    idx = bisect_right(A, (D, 1<<60))

    print(A[idx-1][1])

Submission status: Time Limit Exceeded

Solution code:
n, q = list(map(int, input().split()))
x = sorted([list(map(int,
                     input().split())) for _ in range(n)],
           key=lambda x: x[2])

for _ in range(q):
    d = int(input())
    ans = -1
    for xi in x:
        if xi[0] - 0.5 < xi[2] + d < xi[1] - 0.5:
            ans = xi[2]
            break
    print(ans)

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))
SmXTmXX.sort(lambda x: x[0])
# print(SmXTmXX)
D = []
for i in range(Q):
    d = int(input())
    D.append(d)

ans = [-1] * Q
i = 0
for n in range(N):
    di, dj, x = SmXTmXX[n]
    i = bisect_left(D, di, i)
    j = bisect_left(D, dj, i)
#     print(f"{i} to {j} is out")
    for k in range(i, j):
        ans[k] = x if ans[k] == -1 else min(ans[k], x)
        # print(f"marked {k} as {x}")
for v in ans:
    print(v)

Submission status: Time Limit Exceeded

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

def main():
    n, q = map(int, input().split())
    dic = {}
    stxs = [list(map(int, input().split())) for i in range(n)]
    stxs.sort(key=lambda x:x[2])

    for s, t, x in stxs:
        left = max(0, s - x)
        right = max(0, t - x)

        for i in range(left, right):
            if i not in dic:
                dic[i] = x

    ds = [int(input()) for _ in range(q)]

    for d in ds:
        if d in dic:
            print(dic[d])
        else:
            print(-1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())

con = []
for i in range(n):
	con.append(list(map(int, input().split())))
con = sorted(con, key=lambda x: x[2])

for i in range(q):
	start = int(input())
	final = -1
	for time in con:
		cur = start + time[2]
		if time[0]-0.5<=cur<=time[1]-0.5:
			final = time[2]
			break
	print(final)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import bisect

n,q = na()
xx = []

for i in range(n):
  s,t,x = na()
  xx.append([x,s-0.5-x,t-0.5-x])

xx.sort()
ans = []

for i in range(q):
  d = ni()
  a = -1
  for vl in xx:
      if vl[1] < d and d < vl[2]:
          a = vl[0]
          break
  ans.append(a)

for i in ans:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
n, q = (int(v) for v in input().split())
cons = [tuple([int(v) for v in input().split()]) for _ in range(n)]
times = [int(input()) for _ in range(q)]

fixed_cons = sorted([(s-x, t-x, x) for s, t, x in cons], key=lambda v: v[2])

for st in times:
    flag = True
    for s, t, x in fixed_cons:
        if s <= st and st < t:
            print(x)
            flag = False
            break
    if flag:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return int(input())
from collections import defaultdict
import bisect

n, q = LI()
ss, ts, xs, ds = [], [], [], []
stx = []
ans = [-1 for i in range(q)]
for i in range(n):
    s, t, x = LI()
    stx.append((s, t, x))
for i in range(q):
    d = SI()
    ds.append(d)
stx = sorted(stx, key=lambda x: x[2])
for s, t, x in stx:
    sx = s - x
    tx = t - x
    i1 = bisect.bisect_left(ds, sx)
    i2 = bisect.bisect_left(ds, tx)
    for i in range(i1, i2):
        if ans[i] == -1:
            ans[i] = x
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
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)]
D_kai=[(i,d) for i,d in enumerate(D)]
D_kai.sort(key=lambda x:x[1])
D=[d[1] for d in D_kai]
Dnum=[d[0] for d in D_kai]
kouji_kai=[(max(0,S-X),T-X-1,X) for S,T,X in kouji]
kouji_kai.sort(key=lambda x:x[2])
import bisect
ans=[-1]*Q
checked=set()
for b,e,x in kouji_kai:
    left=bisect.bisect_left(D,b)
    right=bisect.bisect_right(D,e)
    for idx in range(left,right):
        if idx in checked:
            continue
        ans[Dnum[idx]]=x
    checked|={x for x in Dnum[left:right]}
[print(x) for x in ans]

Submission status: Time Limit Exceeded

Solution code:
def mymin(a,b):
    if a==-1:
        return b
    return min(a,b)

n,q=map(int,input().split())
stx=[list(map(int,input().split())) for _ in range(n)]
d=[int(input()) for _ in range(q)]

stop=[-1 for _ in range(q)]
# それぞれの人が工事に遭うかどうか
for i in range(q):
    for j in range(n):
        s,t,x=stx[j]
        # print(i,'人目',j,'工事',d[i],s,t,x)
        if s-0.5 <= x+d[i] <= t-0.5:
            stop[i]=mymin(stop[i],x)
# print(stop)
for s in stop:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
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)]
D_kai=[(i,d) for i,d in enumerate(D)]
D_kai.sort(key=lambda x:x[1])
D=[d[1] for d in D_kai]
Dnum=[d[0] for d in D_kai]
kouji_kai=[(max(0,S-X),T-X-1,X) for S,T,X in kouji]
kouji_kai.sort(key=lambda x:x[2])
import bisect
ans=[-1]*Q
checked=set()
for b,e,x in kouji_kai:
    left=bisect.bisect_left(D,b)
    right=bisect.bisect_right(D,e)
    for idx in range(left,right):
        if idx in checked:
            continue
        ans[Dnum[idx]]=x
    checked|={x for x in Dnum[left:right]}
for i in range(Q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
kl, ql = tuple(map(int,input().split()))

ks = []
for ki in range(kl):
    a,b,x = tuple(map(int,input().split()))
    #a..b-1 nioite x ha tuukou dome
    ks.append((a,b,x))

ds = []
for qi in range(ql):
    d = int(input())
    ds.append(d)


notyetKs = sorted(ks, key=lambda abx:abx[0]-abx[2])
workingKs = []
doneKs = []
"""
doneDSep = 0

t = -1
while doneDSep<len(ds):
    t = min(ds[doneDSep], notyetKs[0][0])
    while True:
"""

for t in ds:
    while len(notyetKs)>0:
        a,b,x = notyetKs[0]
        if a-x <= t:
            if t < b-x:
                workingKs.append((a,b,x))
            else:
                doneKs.append((a,b,x))
            notyetKs.pop(0)
        else:
            break
    workingKs.sort(key=lambda abx: abx[1]-abx[2])
    while len(workingKs)>0:
        a,b,x = workingKs[0]
        if b-x <= t:
            doneKs.append((a,b,x))
            workingKs.pop(0)
        else:
            break

    #print(t, notyetKs,workingKs,doneKs)

    if len(workingKs)==0:
        print(-1)
    else:
        print(sorted(workingKs, key=lambda abx:abx[2])[0][2])

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

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 = {}
for q in querys:
    time[q] = 0

check_parsed = []
for s, f, x in sorted(check_points, key=itemgetter(2)):
    start, end = [s-x, 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:
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]
    
    v, w = ys[0][0], ys[0][1]
    zs = [ys[0]]
    for s, t, x in ys[1:]:
        if s >= v and t <= w:
            pass
        else:
            zs.append((s, t, x))
            pass
        pass

    def doit(xs, d):
        for s, t, x in zs:
            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:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return int(input())
from collections import defaultdict
import bisect

n, q = LI()
ss, ts, xs, ds = [], [], [], []
stx = []
ans = [-1 for i in range(q)]
for i in range(n):
    s, t, x = LI()
    stx.append((s, t, x))
for i in range(q):
    d = SI()
    ds.append(d)
stx = sorted(stx, key=lambda x: x[2])
for s, t, x in stx:
    sx = s - x
    tx = t - x
    i1 = bisect.bisect_left(ds, sx)
    i2 = bisect.bisect_left(ds, tx)
    for i in range(i1, i2):
        if ans[i] == -1:
            ans[i] = x
for i in ans:
    print(i)

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())
	G = ((A-X)<=D)*(D<=(B-X-1))
	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())
L = []
for i in range(N):
    s, t, x = map(int, input().split())
    L.append((s-x, t-x, x))
L = sorted(L, key=lambda p:p[2])


D = []
for i in range(Q):
    D.append(int(input()))



for d in D:
    z = None
    for l in L:
        if l[0] <= d and d < l[1]:
            z = l[2]
            break
    if z is None:
        print(-1)
    else:
        print(z)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())

con = []
for i in range(n):
	con.append(list(map(int, input().split())))
con = sorted(con, key=lambda x: x[2])

for i in range(q):
	start = int(input())

	cont = True
	for time in con:
		loc = time[2]
		cur = start + loc
		if time[0]-0.5<=cur<=time[1]-0.5:
			print(time[2])
			cont = False
			break
	if cont:
		print(-1)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n, q = map(int, input().split())
c = [None] * n
for i in range(n):
  s, t, x = map(int, input().split())
  c[i] = (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())
kouji=[tuple(map(int,input().split())) for i in range(N)]
D=[int(input()) for i in range(Q)]
D_kai=[(i,d) for i,d in enumerate(D)]
D_kai.sort(key=lambda x:x[1])
D=[d[1] for d in D_kai]
Dnum=[d[0] for d in D_kai]
kouji_kai=[(max(0,S-X),T-X-1,X) for S,T,X in kouji]
kouji_kai.sort(key=lambda x:x[2])
import bisect
ans=[-1]*Q
checked=set()
for b,e,x in kouji_kai:
    left=bisect.bisect_left(D,b)
    right=bisect.bisect_right(D,e)
    for idx in range(left,right):
        if idx in checked:
            continue
        ans[Dnum[idx]]=x
    checked|={x for x in Dnum[left:right]}
for i in range(Q):
    print(ans[i])