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:
def main():

    import sys
    import heapq

    N, Q = map(int, sys.stdin.readline().split())
    events = []

    for i in range(N):
        s, t, x = map(int, sys.stdin.readline().split())
        events.append([s - x, 1, x])  # 通行止め追加
        events.append([t - x, -1, x])  # 通行止め削除

    events.sort()
    events.append([float('inf'), 'guard', None])

    i = 0
    closing = set()
    hq = []  # 最小値を高速に入手するため
    for q in range(Q):
        d = int(input())
        while d >= events[i][0]:
            time, event, x = events[i]
            if event == 1:
                closing.add(x)
                heapq.heappush(hq, x)

            elif event == -1:
                closing.remove(x)

            i += 1

        while hq and (hq[0] not in closing):
            heapq.heappop(hq)

        if hq:
            print(hq[0])
        else:
            print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq

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

for i in range(N):
    s, t, x = map(int, sys.stdin.readline().split())
    events.append([s - x, 1, x])  # 通行止め追加
    events.append([t - x, -1, x])  # 通行止め削除

events.sort()
events.append([float('inf'), 'guard', None])

i = 0
closing = set()
hq = []  # 最小値を高速に入手するため
for q in range(Q):
    d = int(input())
    while d >= events[i][0]:
        time, event, x = events[i]
        if event == 1:
            closing.add(x)
            heapq.heappush(hq, x)

        elif event == -1:
            closing.remove(x)

        i += 1

    while hq and (hq[0] not in closing):
        heapq.heappop(hq)

    if hq:
        print(hq[0])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
from collections import defaultdict
N, Q = map(int, input().split())
events = []

for i in range(N):
    s, t, x = map(int, sys.stdin.readline().split())
    events.append([s - x, '2-add', x])
    events.append([t - x, '1-delete', x])

events.sort()
events.append([float('inf'), 'guard', None])

i = 0
closing = set()
hq = []  # 最小値を高速に入手するため
for q in range(Q):
    d = int(input())
    while d >= events[i][0]:
        time, event, x = events[i]
        if event == '2-add':
            closing.add(x)
            heapq.heappush(hq, x)

        elif event == '1-delete':
            closing.remove(x)

        i += 1

    while hq and (hq[0] not in closing):
        heapq.heappop(hq)

    if hq:
        print(hq[0])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import defaultdict
N, Q = map(int, input().split())
events = []

for i in range(N):
    s, t, x = map(int, input().split())
    events.append([s - x, 'add', x])
    events.append([t - x, 'delete', x])

events.sort()
events.append([float('inf'), 'guard', None])

i = 0
closing = defaultdict(int)
hq = []  # 最小値を高速に入手するため
for q in range(Q):
    d = int(input())
    while d >= events[i][0]:
        time, event, x = events[i]
        if event == 'add':
            closing[x] += 1
            heapq.heappush(hq, x)

        elif event == 'delete':
            closing[x] -= 1

        i += 1

    while hq and (closing[hq[0]] == 0):
        heapq.heappop(hq)

    if hq:
        print(hq[0])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, Q = map(int, input().split())
events = []

for i in range(N):
    s, t, x = map(int, input().split())
    events.append([s - x, 'add', x])
    events.append([t - x, 'delete', x])

events.sort()
events.append([float('inf'), 'guard', None])

i = 0
closing_cnt = defaultdict(int)
closing = set()
for q in range(Q):
    d = int(input())
    while d >= events[i][0]:
        time, event, x = events[i]
        if event == 'add':
            closing_cnt[x] += 1
            closing.add(x)
        elif event == 'delete':
            closing_cnt[x] -= 1
            if closing_cnt[x] == 0:
                closing.remove(x)

        i += 1

    if closing:
        print(min(closing))
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop


I = sys.stdin.readlines()
N, Q = map(int, I[0].split())
P = []
for i in range(1, N + 1):
    s, t, x = map(int, I[i].split())
    P.append((s - x, t - 1 - x, x))
P.sort()


q = []
cur = 0
ans = [-1] * Q
for i in range(N + 1, N + Q + 1):
    d = int(I[i])
    while cur < N and P[cur][0] <= d:
        s, t, x = P[cur]
        heappush(q, (x, s, t))
        cur += 1
    while q and q[0][2] < d:
        heappop(q)
    if q:
        ans[i - N - 1] = q[0][0]

print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop


I = sys.stdin.readlines()
N, Q = map(int, I[0].split())
P = []
for i in range(1, N + 1):
    s, t, x = map(int, I[i].split())
    P.append((s - x, t - 1 - x, x))
P.sort()


q = []
cur = 0
for i in range(N + 1, N + Q + 1):
    d = int(I[i])
    while cur < N and P[cur][0] <= d:
        s, t, x = P[cur]
        heappush(q, (x, s, t))
        cur += 1
    ans = -1
    while q and q[0][2] < d:
        heappop(q)
    if q:
        ans = q[0][0]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop


I = sys.stdin.readlines()
N, Q = map(int, I[0].split())
P = []
for i in range(1, N + 1):
    s, t, x = map(int, I[i].split())
    P.append((s - x, t - 1 - x, x))
P.sort()


q = []
cur = 0
for i in range(N + 1, N + Q + 1):
    d = int(I[i])
    while cur < N and P[cur][0] <= d:
        s, t, x = P[cur]
        heappush(q, (x, s, t))
        cur += 1
    ans = -1
    while q:
        if d <= q[0][2]:
            ans = q[0][0]
            break
        else:
            heappop(q)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop


I = sys.stdin.readlines()
N, Q = map(int, I[0].split())
P = []
for i in range(1, N + 1):
    s, t, x = map(int, I[i].split())
    P.append((s - x, t - 1 - x, x))
P.sort()


q = []
cur = 0
cnt = 0
for i in range(N + 1, N + Q + 1):
    d = int(I[i])
    while cur < N and P[cur][0] <= d:
        s, t, x = P[cur]
        heappush(q, (x, s, t))
        cnt += 1
        cur += 1
    ans = -1
    while cnt:
        if d <= q[0][2]:
            ans = q[0][0]
            break
        else:
            heappop(q)
            cnt -= 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush, heappop


I = sys.stdin.readlines()
N, Q = map(int, I[0].split())
P = []
for i in range(1, N + 1):
    s, t, x = map(int, I[i].split())
    P.append((s - x, t - 1 - x, x))
P.sort()


q = []
cur = 0
for i in range(N + 1, N + Q + 1):
    d = int(I[i])
    while cur < N and P[cur][0] <= d:
        s, t, x = P[cur]
        heappush(q, (x, s, t))
        cur += 1
    ans = -1
    while len(q) > 0:
        if d <= q[0][2]:
            ans = q[0][0]
            break
        else:
            heappop(q)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,q=map(int,input().split())
# STX=[tuple(map(int,input().split())) for i in range(n)]
# D=[int(input()) for i in range(q)]
event=[]
for i in range(n):
  si,ti,xi = map(int,input().split())
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for i in range(q):
  di=int(input())
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      print(-1)
    else:
      print(hq[0])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline()
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
ans = []
for time, query, number in event:
  if query == 0:
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      ans.append(-1)
    else:
      ans.append(hq[0])
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      print(-1)
    else:
      print(hq[0])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    # print("#F")
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    # print(S,number)
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      print(-1)
    else:
      print(hq[0])

Submission status: Time Limit Exceeded

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

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

ans=[-1]*Q
for X,S,T in XST:
    s,t=S-X,T-X
    left=bisect(D,[s])
    right=bisect(D,[t])
    
    for i in range(left,right):
        ans[D[i][1]]=X
    D=D[:left]+D[right:]
    
for u in ans:
    print(u)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect

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

ans=[-1]*Q
for X,S,T in XST:
    s,t=S-X,T-X
    left=bisect(D,[s])
    right=bisect(D,[t])
    
    for i in range(left,right):
        ans[D[i][1]]=X
    D=D[:left]+D[right:]
    
for u in ans:
    print(u)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
stx = [0]*N
for n in range(N):
    stx[n] = list(map(int, input().split()))
stx.sort(key=lambda x: x[2])

qs = [0]*Q
for q in range(Q):
    qs[q] = int(input())

answer = [-1]*Q
for i in stx:
    for j in range(i[0]-i[2],i[1]-i[2]):
        if j<0: continue
        if j in qs:
            ind = qs.index(j)
            answer[ind] = i[2]
            qs[ind] = -1
for i in answer:
    print(i)

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 _ in range(n)]
d = [int(input())  for _ in range(q)]

ans = [-1] * q
l = []

for si, ti, xi in stx:
  l.append((si-xi, 1, xi))
  l.append((ti-xi, 0, xi))

for i, d in enumerate(d):
  l.append((d, 2, i))

l.sort()

hoge = set()

for a, b, c in l:
  if b == 0:
    hoge.remove(c)
  elif b == 1:
    hoge.add(c)
  elif b == 2:
    if hoge:
      ans[c] = min(hoge)

for a in ans:
  print(a)

Submission status: Time Limit Exceeded

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

ans = [-1] * q
l = []

for si, ti, xi in stx:
  l.append((si-xi, 1, xi))
  l.append((ti-xi, 0, xi))

for i, d in enumerate(d):
  l.append((d, 2, i))

l.sort()

hoge = set()

for a, b, c in l:
  if b == 0:
    hoge.remove(c)
  elif b == 1:
    hoge.add(c)
  elif b == 2:
    if hoge:
      ans[c] = min(hoge)

for a in ans:
  print(a)

Submission status: Time Limit Exceeded

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

ans = [-1] * q
l = []

for si, ti, xi in stx:
  l.append((si-xi, 1, xi))
  l.append((ti-xi, 0, xi))

for i, d in enumerate(d):
  l.append((d, 2, i))

l.sort()

hoge = set()

for a, b, c in l:
  if b == 0:
    hoge.remove(c)
  elif b == 1:
    hoge.add(c)
  elif b == 2:
    if hoge:
      ans[c] = min(hoge)

for a in ans:
  print(a)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

ans = [-1] * q

for si, ti, xi in stx:
  l = bisect.bisect_left(d, si - xi, lo=0, hi=q)
  r = bisect.bisect_left(d, ti - xi, lo=0, hi=q)
  for i in range(l, r):
    if ans[i] == -1:
      ans[i] = xi


for a in ans:
  print(a)

Submission status: Time Limit Exceeded

Solution code:
import heapq

n, q = map(int, input().split())
events = []
for _ in range(n):
    s, t, x = map(int, input().split())
    events.append((s - x, x, 1))
    events.append((t - x, x, -1))
events.append((10000000000, 0, 0))
events.sort()
d = []
for _ in range(q):
    d.append(int(input()))

xlist = []
xset = set()
i = 0
for j in range(q):
    while events[i][0] <= d[j]:
        t, x, a = events[i]
        if a == 1:
            xset.add(x)
            heapq.heappush(xlist, x)
        else:
            xset.remove(x)
            while xlist and not xlist[0] in xset:
                heapq.heappop(xlist)
        i += 1
    if xlist:
        print(xlist[0])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq

n, q = map(int, input().split())
events = []
for _ in range(n):
    s, t, x = map(int, input().split())
    events.append((s - x, x, 1))
    events.append((t - x, x, -1))
events.append((10000000000, 0, 0))
events.sort()

xlist = []
xset = set()
i = 0
for _ in range(q):
    d = int(input())
    while events[i][0] <= d:
        t, x, a = events[i]
        if a == 1:
            xset.add(x)
            heapq.heappush(xlist, x)
        else:
            xset.remove(x)
            while xlist and not xlist[0] in xset:
                heapq.heappop(xlist)
        i += 1
    if xlist:
        print(xlist[0])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq

n, q = map(int, input().split())
stx = [list(map(int, input().split())) for _ in range(n)]
events = sorted([(s - x, x, 1) for s, t, x in stx] + [(t - x, x, -1) for s, t, x in stx])
events.append((10000000000, 0, 0))

xlist = []
xset = set()
i = 0
for _ in range(q):
    d = int(input())
    while events[i][0] <= d:
        t, x, a = events[i]
        if a == 1:
            xset.add(x)
            heapq.heappush(xlist, x)
        else:
            xset.remove(x)
            while xlist and not xlist[0] in xset:
                heapq.heappop(xlist)
        i += 1
    if xlist:
        print(xlist[0])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq

n, q = map(int, input().split())
stx = [list(map(int, input().split())) for _ in range(n)]
events = sorted([(s - x, x, 1) for s, t, x in stx] + [(t - x, x, -1) for s, t, x in stx])

xlist = []
xset = set()
i = 0
for _ in range(q):
    d = int(input())
    while i < 2 * n and events[i][0] <= d:
        t, x, a = events[i]
        if a == 1:
            xset.add(x)
            heapq.heappush(xlist, x)
        else:
            xset.remove(x)
            while len(xlist) > 0 and not xlist[0] in xset:
                heapq.heappop(xlist)
        i += 1
    if len(xlist) == 0:
        print(-1)
    else:
        print(xlist[0])

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

i = 0
tx = []
xt = []
for _ in range(q):
    d = int(input())
    while i < n and stx[i][0] <= d:
        s, t, x = stx[i]
        bisect.insort(tx, (t, x))
        bisect.insort(xt, (x, t))
        i += 1
    while len(tx) > 0 and tx[0][0] <= d:
        t, x = tx[0]
        del tx[bisect.bisect_left(tx, (t, x))]
        del xt[bisect.bisect_left(xt, (x, t))]
    if len(xt) == 0:
        print(-1)
    else:
        x, t = xt[0]
        print(x)

Submission status: Time Limit Exceeded

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

def main():
  n, q = map(int, input().split())
  event = []
  stop = set()
  for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s-x, 1, x))
    event.append((t-x, -1, x))
  event.sort()
  event.append((float("inf"), 0, 0))
  D = list(map(int, read().split()))
  now = 0
  for t, b, x in event:
    m = min(stop) if stop else -1
    while t > D[now]:
      print(m)
      now += 1
      if now == q:
        exit()
    if b == 1:
      stop.add(x)
    else:
      stop.remove(x)
      
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

def main():
  n, q = map(int, input().split())
  event = []
  stop = set()
  for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s-x, 1, x))
    event.append((t-x, -1, x))
  event.sort()
  event.append((float("inf"), 0, 0))
  D = list(map(int, read().split()))
  now = 0
  for t, b, x in event:
    while t > D[now]:
      if stop:
        print(min(stop))
      else:
        print(-1)
      now += 1
      if now == q:
        exit()
    if b == 1:
      stop.add(x)
    else:
      stop.remove(x)
      
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
event = []
stop = set()
for _ in range(n):
  s, t, x = map(int, input().split())
  event.append((s-x, 1, x))
  event.append((t-x, -1, x))
event.sort()
event.append((float("inf"), 0, 0))
D = [int(input()) for _ in range(q)]
now = 0
for t, b, x in event:
  while t > D[now]:
    if stop:
      print(min(stop))
    else:
      print(-1)
    now += 1
    if now == q:
      exit()
  if b == 1:
    stop.add(x)
  else:
    stop.remove(x)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
STX = [tuple(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

starts = []
ends = []
for i,(s,t,x) in enumerate(STX):
    starts.append((s-x,i))
    ends.append((t-x,i))
starts.sort(key=lambda x:x[0], reverse=True)
ends.sort(key=lambda x:x[0], reverse=True)

import heapq
hq = []
heapq.heapify(hq)
delset = set()

ans = []
for d in D:
    while starts and starts[-1][0] <= d:
        _,i = starts.pop()
        x = STX[i][2]
        heapq.heappush(hq, (x,i))
    while ends and ends[-1][0] <= d:
        _,i = ends.pop()
        delset.add(i)
    while hq:
        _,i = hq[0]
        if i in delset:
            heapq.heappop(hq)
        else:
            break
    if len(hq)==0:
        ans.append(-1)
    else:
        x,i = hq[0]
        ans.append(x)

print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
STX = [tuple(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

starts = []
ends = []
for i,(s,t,x) in enumerate(STX):
    starts.append((s-x,i))
    ends.append((t-x,i))
starts.sort(reverse=True)
ends.sort(reverse=True)

import heapq
hq = []
heapq.heapify(hq)
delset = set()

ans = []
for d in D:
    while starts and starts[-1][0] <= d:
        _,i = starts.pop()
        x = STX[i][2]
        heapq.heappush(hq, (x,i))
    while ends and ends[-1][0] <= d:
        _,i = ends.pop()
        delset.add(i)
    while hq:
        _,i = hq[0]
        if i in delset:
            heapq.heappop(hq)
        else:
            break
    if len(hq)==0:
        ans.append(-1)
    else:
        x,i = hq[0]
        ans.append(x)

print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappush,heappop
input=sys.stdin.readline
n,q=map(int,input().split())
e=[]
for i in range(n):
  s,t,x=map(int,input().split())
  e.append((s-x,1,x))
  e.append((t-x,-1,x))
for i in range(q):
  d=int(input())
  e.append((d,2,0))
e.sort()
s=set()
a=[]
for time_,type_,x_ in e:
  if type_==1:
    s.add(x_)
    heappush(a,x_)
  elif type_==-1:
    s.remove(x_)
  else:
    while a and a[0] not in s:
      heappop(a)
    if a:
      print(a[0])
    else:
      print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
n,q=map(int,input().split())
e=[]
for i in range(n):
  s,t,x=map(int,input().split())
  e.append((s-x,1,x))
  e.append((t-x,-1,x))
for i in range(q):
  d=int(input())
  e.append((d,2,0))
e.sort()
s=set()
a=[]
for time_,type_,x_ in e:
  if type_==1:
    s.add(x_)
    heappush(a,x_)
  elif type_==-1:
    s.remove(x_)
  else:
    while a and a[0] not in s:
      heappop(a)
    if a:
      print(a[0])
    else:
      print(-1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
n,q=map(int,input().split())
e=[]
for i in range(n):
  s,t,x=map(int,input().split())
  e.append([s-x,1,x])
  e.append([t-x,-1,x])
for i in range(q):
  d=int(input())
  e.append([d,2,0])
e.sort()
s=set()
a=[]
for time_,type_,x_ in e:
  if type_==1:
    s.add(x_)
    heappush(a,x_)
  elif type_==-1:
    s.remove(x_)
  else:
    while a and a[0] not in s:
      heappop(a)
    if a:
      print(a[0])
    else:
      print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N,Q = list(map(int,input().split()))

    road = []
    x_list = []

    for i in range(N):
        s,t,x = list(map(int,input().split()))
        road.append([0,s-x,x])
        road.append([1,t-x,x])

    for i in range(Q):
        road.append([2,int(input()),i])

    from collections import defaultdict

    counter = defaultdict(int)
    counter[10**27] = 1
    ans = [0]*Q

    road.sort(key=lambda x:x[0])
    road.sort(key=lambda x:x[1])

    q = [10**27]

    from heapq import heappop,heappush

    for id,_,x in road:
        if id==0:
            heappush(q,x)
            counter[x]+=1
        elif id==1:
            counter[x]-=1
        else:
            while counter[q[0]]==0:
                heappop(q)
            #print(q)
            if q[0]<10**27:
                ans[x] = q[0]
            else:
                ans[x] = -1
    print("\n".join(map(str,ans)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

road = []
x_list = []

for i in range(N):
    s,t,x = list(map(int,input().split()))
    road.append([0,s-x,x])
    road.append([1,t-x,x])

for i in range(Q):
    road.append([2,int(input()),i])

from collections import defaultdict

counter = defaultdict(int)
counter[10**27] = 1
ans = [0]*Q

road.sort(key=lambda x:x[0])
road.sort(key=lambda x:x[1])

q = [10**27]

from heapq import heappop,heappush

for id,_,x in road:
    if id==0:
        heappush(q,x)
        counter[x]+=1
    elif id==1:
        counter[x]-=1
    else:
        while counter[q[0]]==0:
            heappop(q)
        #print(q)
        if q[0]<10**27:
            ans[x] = q[0]
        else:
            ans[x] = -1
print("\n".join(map(str,ans)))

Submission status: Time Limit Exceeded

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

road = []
x_list = []

for i in range(N):
    s,t,x = list(map(int,input().split()))
    road.append([0,s-x,x])
    road.append([1,t-x,x])

for i in range(Q):
    road.append([2,int(input()),i])

from collections import defaultdict

counter = defaultdict(int)
counter[10**27] = 1
ans = [0]*Q

#road.sort(key=lambda x:x[0])
road.sort(key=lambda x:x[1])

q = [10**27]

from heapq import heappop,heappush

for id,_,x in road:
    if id==0:
        heappush(q,x)
        counter[x]+=1
    elif id==1:
        counter[x]-=1
    else:
        while counter[q[0]]==0:
            heappop(q)
        #print(q)
        if q[0]<10**27:
            ans[x] = q[0]
        else:
            ans[x] = -1
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

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

road = []
x_list = []

for i in range(N):
    s,t,x = list(map(int,input().split()))
    road.append([0,s-x,x])
    road.append([1,t-x,x])

for i in range(Q):
    road.append([2,int(input()),i])

from collections import defaultdict

counter = defaultdict(int)
counter[10**27] = 1
ans = [0]*Q

road.sort(key=lambda x:x[0])
road.sort(key=lambda x:x[1])

q = [10**27]

from heapq import heappop,heappush

for id,_,x in road:
    if id==0:
        heappush(q,x)
        counter[x]+=1
    elif id==1:
        counter[x]-=1
    else:
        while counter[q[0]]==0:
            heappop(q)
        #print(q)
        if q[0]<10**27:
            ans[x] = q[0]
        else:
            ans[x] = -1
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N,Q = list(map(int,input().split()))

    road = []
    x_list = []

    for i in range(N):
        s,t,x = list(map(int,input().split()))
        road.append([0,s-x,x])
        road.append([1,t-x,x])
        x_list.append(x)

    for i in range(Q):
        road.append([2,int(input()),i])

    x_list.sort()

    from collections import defaultdict
    dd1 = defaultdict(int)
    dd2 = defaultdict(int)

    count = -1
    prev = -1
    for i in range(N):
        if x_list[i]!=prev:
            prev=x_list[i]
            count+=1
        dd1[x_list[i]] = count
        dd2[count] = x_list[i]

    class BIT:
                
        def __init__(self, L):
            self.N = len(L)
            self.bit = [0]*self.N
            for i,l in enumerate(L):
                self.add(i,l)

        def add(self, a, w):
            x = a + 1
            for i in range(1000):
                self.bit[x-1] += w
                x += x & -x
                if x > self.N:
                    break

        def sum(self, a):
            x = a+1
            ret = 0
            for i in range(1000):
                ret += self.bit[x-1]
                x -= x & -x
                if x <= 0:
                    break        
            return ret

    bit = BIT([0]*(count+1))

    def get_zero():
        B = bit.sum(count)
        C = bit.sum(0)
        if B==0:
            return count+1
        elif C>=1:
            return 0
        else:
            l = 0
            r = count
            while r-l>1:
                if bit.sum((l+r)//2) >= 1:
                    r = (l+r)//2
                else:
                    l = (l+r)//2
            return r

    road.sort(key = lambda x:x[0])
    road.sort(key = lambda x:x[1])
    #print(road)
    ans = [0]*Q

    for obj in road:
        if obj[0]==0:
            bit.add(dd1[obj[2]], 1)
        elif obj[0]==1:
            bit.add(dd1[obj[2]], -1)
        else:
            #print(*[bit.sum(i) for i in range(3)])
            r = get_zero()
            if r==count+1:
                ans[obj[2]] = -1
            else:
                ans[obj[2]] = dd2[r]

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




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, q = [int(i) for i in input().split()]
blockers = []
for _ in range(n):
    t1, t2, p = [int(i) for i in input().split()]
    blockers.append([t1 - p, t2 - p - 1, p])

computed = {}
starts = [int(input()) for _ in range(q)]
for d in starts:
    if d in computed:
        print(computed[d])
        continue

    pos = -1
    for b in blockers:
        if (pos == -1 or pos > b[2]) and d >= b[0] and d <= b[1]:
            pos = b[2]

    print(pos)

Submission status: Time Limit Exceeded

Solution code:
n, q = [int(i) for i in input().split()]
roadworks = []
for _ in range(n):
    roadworks.append([int(i) for i in input().split()])
roadworks.sort(key=lambda r: r[2])

blockers = []
for r in roadworks:
    blockers.append({"begin": r[0] - r[2], "end": r[1] - r[2] - 1, "pos": r[2]})


starts = []
for _ in range(q):
    starts.append(int(input()))

computed = {}
for d in starts:
    if d in computed:
        print(computed[d])
        continue

    will_stop = -1
    for b in blockers:
        if d >= b["begin"] and d <= b["end"]:
            will_stop = b["pos"]
            break

    computed[d] = will_stop
    print(will_stop)