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 sys
#import numpy as np
import bisect
sys.setrecursionlimit(10 ** 7)

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

PEOPLE = []
for _ in range(Q):
    d = int(input())
    PEOPLE.append(d)

ans = [str(-1)] * Q

STX.sort(key=lambda x: x[2])

for s, t, x in STX:
    #print("s,t,x", s, t, x)
    #i = np.searchsorted(PEOPLE, s - x)
    #j = np.searchsorted(PEOPLE, t - x)
    i = bisect.bisect_left(PEOPLE, s - x)
    j = bisect.bisect_left(PEOPLE, t - x)
    #print("i,j", i, j)

    for k in range(i, j):
        if ans[k] == '-1':
            ans[k] = str(x)

    # print(ans)

print("\n".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

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

PEOPLE = []
for _ in range(Q):
    d = int(input())
    PEOPLE.append(d)

ans = [str(-1)] * Q

STX.sort(key=lambda x: x[2])

for s, t, x in STX:
    #print("s,t,x", s, t, x)
    i = np.searchsorted(PEOPLE, s - x)
    j = np.searchsorted(PEOPLE, t - x)
    #print("i,j", i, j)

    for k in range(i, j):
        if ans[k] == '-1':
            ans[k] = str(x)

    # print(ans)

print("\n".join(ans))

Submission status: Time Limit Exceeded

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

N, Q = (int(i) for i in input().split())
L = [0] * 2 * N
P = {}
for i in range(N):
    S, T, X = (int(i) for i in input().split())
    L[2 * i] = (S-X, X, 1)
    L[2 * i + 1] = (T-X, X, 0)

L.sort(reverse=True)

Xs = set([])
for i in range(Q):
    D = int(input())
    ans = 0
    while True:
        if not L:
            break
        tp = L.pop()
        t = tp[0]
        if t <= D:
            if tp[2] == 1:
                Xs.add(tp[1])
            else:
                Xs.remove(tp[1])
        else:
            L.append(tp)
            break
    if Xs:
        print(min(Xs))
    else:
        print("-1")

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, Q = (int(i) for i in input().split())
L = [0] * (2 * N + Q)
for i in range(N):
    S, T, X = (int(i) for i in input().split())
    L[2 * i] = (S-X, X, 1)
    L[2 * i + 1] = (T-X, X, -1)
for i in range(Q):
    D = int(input())
    L[2 * N + i] = (D, 10**9+1, 0)
L.sort()

Xs = set([])
XH = []
heapq.heapify(XH)
for t, X, f in L:
    if f == 1:
        Xs.add(X)
        heapq.heappush(XH, X)
    elif  f == -1:
        Xs.remove(X)
    else:
        if Xs:
            while XH[0] not in Xs:
                X = heapq.heappop(XH)
            print(XH[0])
        else:
            print("-1")

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, Q = (int(i) for i in input().split())
L = [0] * 2 * N
for i in range(N):
    S, T, X = (int(i) for i in input().split())
    L[2 * i] = (S-X, X, 1)
    L[2 * i + 1] = (T-X, X, 0)

L.sort(reverse=True)

Xs = set([])
XH = []
heapq.heapify(XH)
for i in range(Q):
    D = int(input())
    ans = 0
    while True:
        if L:
            t, X, f = L.pop()
            if t <= D:
                if f == 1:
                    Xs.add(X)
                    heapq.heappush(XH, X)
                else:
                    Xs.remove(X)
            else:
                L.append((t, X, f))
                break
        else:
            break
    if Xs:
        while XH[0] not in Xs:
            X = heapq.heappop(XH)
        print(XH[0])
    else:
        print("-1")

Submission status: Time Limit Exceeded

Solution code:
import sys
 
input = sys.stdin.readline
N, Q = map(int, input().split())
event_list = []
for i in range(N):
  s, t, x = map(int, input().split())
  event_list.append([s-x, 1, x])
  event_list.append([t-x, -1, x])

event_list.sort()
event_list.append([10**10, 1, 10**10])
i = 0
x_set = set()
for q in range(Q):
  d = int(input())
  while True:
    time, event, x = event_list[i]
    if time <= d:
      if event == 1:
        x_set.add(x)
      else:
        x_set.discard(x)
      i += 1
    else:
      break
  if x_set:
    print(min(x_set))
  else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N, Q = (int(i) for i in input().split())
L = [0] * 2 * N
for i in range(N):
    S, T, X = (int(i) for i in input().split())
    L[2 * i] = (S-X, X, 1)
    L[2 * i + 1] = (T-X, X, 0)

L.sort(reverse=True)

Xs = set([])
for i in range(Q):
    D = int(input())
    ans = 0
    while True:
        if L:
            t, X, f = L.pop()
            if t <= D:
                if f == 1:
                    Xs.add(X)
                else:
                    Xs.remove(X)
            else:
                L.append((t, X, f))
                break
        else:
            break
    if Xs:
        print(min(Xs))
    else:
        print("-1")

Submission status: Time Limit Exceeded

Solution code:
N, Q = (int(i) for i in input().split())
L = [0] * 2 * N
P = {}
for i in range(N):
    S, T, X = (int(i) for i in input().split())
    L[2 * i] = (S-X, X, 1)
    L[2 * i + 1] = (T-X, X, 0)

L.sort(reverse=True)

Xs = set([])
for i in range(Q):
    D = int(input())
    ans = 0
    while True:
        if not L:
            break
        tp = L.pop()
        t = tp[0]
        if t <= D:
            if tp[2] == 1:
                Xs.add(tp[1])
            else:
                Xs.remove(tp[1])
        else:
            L.append(tp)
            break
    if Xs:
        print(min(Xs))
    else:
        print("-1")

Submission status: Time Limit Exceeded

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

from heapq import heappop, heappush

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

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

ans = []
event_list.sort()
x_set = set()
x_list = []
for time, event, x in event_list:
  if event == 1:
    x_set.add(x)
    heappush(x_list, x)
  elif event == -1:
    x_set.remove(x)
  else:
    while x_list and x_list[0] not in x_set:
      heappop(x_list)
    if x_list:
      ans.append(x_list[0])
    else:
      ans.append(-1)

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

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())
# stx = [tuple(map(int, input().split())) for _ in range(n)]
stx = [0]*n
for i in range(n):
    stx[i] = tuple(map(int, input().split()))
# d = [int(input()) for _ in range(q)]
d = [0]*q
for i in range(q):
    d[i] = int(input())

#これはセグ木 * bisect
import bisect
inf = 10**9 + 100

# 定数倍高速化
b_left = bisect.bisect_left
b_right = bisect.bisect_right

def init(n,init_num=0):
    num = len(str(bin(n-1))) + 1
    seg = [init_num] * (2**num)
    # seg[0] = 2**(num-1)
    seg0 = 2**(num-1)
    return(seg,seg0)

def update(head, tail, x):
    # print('{} {} {}'.format(head, tail, x))
    head += seg0
    tail += seg0
    points = []
    while(head <= tail):
        if(head == tail):
            points.append(head)
            break

        if(head % 2 ==1):
            points.append(head)
            head += 1
        head = head//2

        if(tail % 2 == 0):
            points.append(tail)
            tail -= 1
        tail = (tail-1)//2

    for point in points:
        seg[point] = min(seg[point], x)

def execute_all():
    for i in range(2,len(seg)):
        seg[i] = min(seg[i], seg[i//2])


seg,seg0 = init(q, init_num = inf)

for i in range(n):
    left = b_left(d, stx[i][0] -stx[i][2])
    right = b_right(d, stx[i][1] - stx[i][2] -1) -1
    update(left, right, stx[i][2])
    # print('{} {} {}'.format(left, right, stx[i][2]))

execute_all()

for i in seg[seg0: seg0 + q]:
    if(i == inf):
        print(-1)
    else:
        print(i)

Submission status: Time Limit Exceeded

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

#これはセグ木 * bisect
import bisect
inf = 10**9 + 100

def init(n,init_num=0):
    num = len(str(bin(n-1))) + 1
    seg = [init_num] * (2**num)
    seg[0] = 2**(num-1)
    return(seg)

def update(head, tail, x):
    # print('{} {} {}'.format(head, tail, x))
    head += seg[0]
    tail += seg[0]
    points = []
    while(head <= tail):
        if(head == tail):
            points.append(head)
            break

        if(head % 2 ==1):
            points.append(head)
            head += 1
        head = head//2

        if(tail % 2 == 0):
            points.append(tail)
            tail -= 1
        tail = (tail-1)//2

    for point in points:
        seg[point] = min(seg[point], x)

def execute(p):
    p += seg[0]
    tmp = seg[p]
    while(p > 0):
        p = p//2
        tmp = min(tmp, sep[p])
    return(tmp)

def execute_all():
    for i in range(2,len(seg)):
        seg[i] = min(seg[i], seg[i//2])


seg = init(q, init_num = inf)

for i in range(n):
    left = bisect.bisect_left(d, stx[i][0] -stx[i][2])
    right = bisect.bisect_right(d, stx[i][1] - stx[i][2] -1) -1
    update(left, right, stx[i][2])
    # print('{} {} {}'.format(left, right, stx[i][2]))

execute_all()

for i in seg[seg[0]: seg[0] + q]:
    if(i == inf):
        print(-1)
    else:
        print(i)

Submission status: Time Limit Exceeded

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

#これはセグ木 * bisect
import bisect
inf = 10**9 + 100

def init(n,init_num=0):
    num = len(str(bin(n-1))) + 1
    seg = [init_num] * (2**num)
    seg[0] = 2**(num-1)
    return(seg)

def update(head, tail, x):
    # print('{} {} {}'.format(head, tail, x))
    head += seg[0]
    tail += seg[0]
    points = []
    while(head <= tail):
        if(head == tail):
            points.append(head)
            break

        if(head % 2 ==1):
            points.append(head)
            head += 1
        head = head//2

        if(tail % 2 == 0):
            points.append(tail)
            tail -= 1
        tail = (tail-1)//2

    for point in points:
        seg[point] = min(seg[point], x)

def execute(p):
    p += seg[0]
    tmp = seg[p]
    while(p > 0):
        p = p//2
        tmp = min(tmp, sep[p])
    return(tmp)

def execute_all():
    for i in range(2,len(seg)):
        seg[i] = min(seg[i], seg[i//2])


seg = init(q, init_num = inf)

for i in range(n):
    left = bisect.bisect_left(d, stx[i][0] -stx[i][2])
    right = bisect.bisect_right(d, stx[i][1] - stx[i][2] -1) -1
    update(left, right, stx[i][2])
    # print('{} {} {}'.format(left, right, stx[i][2]))

execute_all()

for i in seg[seg[0]: seg[0] + q]:
    if(i == inf):
        print(-1)
    else:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
import heapq
def main():
    N, Q = map(int, input().split())
    ls = []
    lt = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        ls.append((s-x, x))
        lt.append((t-x, x))
    ls.sort(reverse=True)
    lt.sort(reverse=True)
    dh = []
    dl = []
    for i in range(Q):
        d = int(input())
        while ls and ls[-1][0] <= d:
            s, x = ls.pop()
            heapq.heappush(dl, x)
        while lt and lt[-1][0] <= d:
                t, x = lt.pop()
                heapq.heappush(dh, x)
        while dl and dh and dl[0] == dh[0]:
            heapq.heappop(dl)
            heapq.heappop(dh)
        if not dl:
            print('-1')
        else:
            print(dl[0])
main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
def main():
    N, Q = map(int, input().split())
    ls = []
    lt = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        ls.append((s-x, x))
        lt.append((t-x, x))
    ls.sort(reverse=True, key=lambda x: x[0])
    lt.sort(reverse=True, key=lambda x: x[0])
    dh = []
    dl = []
    heapq.heapify(dh)
    heapq.heapify(dl)
    for i in range(Q):
        d = int(input())
        while len(ls) > 0 and ls[-1][0] <= d:
            s, x = ls.pop()
            heapq.heappush(dl, x)
        while len(lt) > 0 and lt[-1][0] <= d:
                t, x = lt.pop()
                heapq.heappush(dh, x)
        while len(dl) > 0 and len(dh) > 0 and dl[0] == dh[0]:
            heapq.heappop(dl)
            heapq.heappop(dh)
        if not dl:
            print('-1')
        else:
            print(dl[0])
main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush

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

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

ans = []
event_list.sort()
x_set = set()
x_list = []
for time, event, x in event_list:
  if event == 1:
    x_set.add(x)
    heappush(x_list, x)
  elif event == -1:
    x_set.remove(x)
  else:
    while x_list and x_list[0] not in x_set:
      heappop(x_list)
    if x_list:
      ans.append(x_list[0])
    else:
      ans.append(-1)

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush

N,Q=map(int,input().split())
E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append((s-x,1,x))
    E.append((t-x,0,x))

for a in range(Q):
    E.append((int(input()),2,0))
E.sort()
 
S=set()
H=[]
for time_,type_,x in E:
    if type_==1:
        S.add(x)
        heappush(H,x)
    elif type_==0:
        S.remove(x)
    else:
        while H and H[0] not in S:
            heappop(H)
        print(H[0] if H else -1)

Submission status: Time Limit Exceeded

Solution code:
# これは間に合うの？

from heapq import heappop,heappush
N,Q=map(int,input().split())
E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append((s-x,1,x))
    E.append((t-x,0,x))

for a in range(Q):
    E.append((int(input()),2,0))
E.sort()
 
S=set()
H=[]
for time_,type_,x in E:
    if type_==1:
        S.add(x)
        heappush(H,x)
    elif type_==0:
        S.remove(x)
    else:
        while H and H[0] not in S:
            heappop(H)
        print(H[0] if H else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush

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

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

event_list.sort()
x_set = set()
x_list = []
for time, event, x in event_list:
  if event == 1:
    x_set.add(x)
    heappush(x_list, x)
  elif event == -1:
    x_set.remove(x)
  else:
    while x_list and x_list[0] not in x_set:
      heappop(x_list)
    if x_list:
      print(x_list[0])
    else:
      print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq


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

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

event_list.sort()
event_list.append([10**10, 1, 10**10])

x_set = set()
x_list = []
for time, event, x in event_list:
  if event == 1:
    x_set.add(x)
    heapq.heappush(x_list, x)
  elif event == -1:
    x_set.remove(x)
  else:
    while x_list and x_list[0] not in x_set:
      heapq.heappop(x_list)
    if x_list:
      print(x_list[0])
    else:
      print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq


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

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

event_list.sort()
event_list.append([10**10, 1, 10**10])

x_set = set()
x_list = []
for time, event, x in event_list:
  if event == 1:
    x_set.add(x)
    heapq.heappush(x_list, x)
  elif event == -1:
    x_set.remove(x)
  else:
    while x_list and x_list[0] not in x_set:
      _ = heapq.heappop(x_list)
    if x_list:
      print(x_list[0])
    else:
      print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq


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

event_list.sort()
event_list.append([10**10, 1, 10**10])
i = 0
x_set = set()
x_list = []
time = 0
for q in range(Q):
  d = int(input())
  while time <= d:
    time, event, x = event_list[i]
    if time <= d:
      if event == 1:
        x_set.add(x)
        heapq.heappush(x_list, x)
      else:
        x_set.remove(x)
      i += 1
  
  while x_list and x_list[0] not in x_set:
    _ = heapq.heappop(x_list)
  if x_list:
    print(x_list[0])
  else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq


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

event_list.sort()
event_list.append([10**10, 1, 10**10])
i = 0
x_set = set()
x_list = []
time = 0
for q in range(Q):
  d = int(input())
  while time <= d:
    time, event, x = event_list[i]
    if time <= d:
      if event == 1:
        x_set.add(x)
        heapq.heappush(x_list, x)
      else:
        x_set.remove(x)
      i += 1
  if x_set:
    while x_list and x_list[0] not in x_set:
      _ = heapq.heappop(x_list)
    print(x_list[0])
  else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq


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

event_list.sort()
event_list.append([10**10, 1, 10**10])
i = 0
x_set = set()
x_list = []
for q in range(Q):
  d = int(input())
  while True:
    time, event, x = event_list[i]
    if time <= d:
      if event == 1:
        x_set.add(x)
        heapq.heappush(x_list, x)
      else:
        x_set.remove(x)
      i += 1
    else:
      break
  if x_set:
    while x_list and x_list[0] not in x_set:
      _ = heapq.heappop(x_list)
    print(x_list[0])
  else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq


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

event_list.sort()
event_list.append([10**10, 1, 10**10])
i = 0
x_set = set()
x_list = []
for q in range(Q):
  d = int(input())
  while True:
    time, event, x = event_list[i]
    if time <= d:
      if event == 1:
        x_set.add(x)
        heapq.heappush(x_list, x)
      else:
        x_set.discard(x)
      i += 1
    else:
      break
  if x_set:
    while x_list and x_list[0] not in x_set:
      _ = heapq.heappop(x_list)
    print(x_list[0])
  else:
    print(-1)

Submission status: Time Limit Exceeded

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

event_list.sort()
event_list.append([10**10, 1, 10**10])
i = 0
x_set = set()
for q in range(Q):
  d = int(input())
  while True:
    time, event, x = event_list[i]
    if time <= d:
      if event == 1:
        x_set.add(x)
      else:
        x_set.discard(x)
      i += 1
    else:
      break
  if x_set:
    print(min(x_set))
  else:
    print(-1)

Submission status: Time Limit Exceeded

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

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

    for i in range(N):
        S, T, X = map(int, input().split())
        event.append([S-X-0.5, 0, X])
        event.append([T-X-0.5, 1, X])
    event = sorted(event)

    D = [int(input()) for i in range(Q)]
    n = []
    idx = 0

    for d in D:
        while idx < 2*N and event[idx][0] < d:
            _, m, x = event[idx]
            idx += 1

            if m == 0: insort_left(n, x)
            else: del n[bisect_left(n, x)]

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
from bisect import *
import sys
input = sys.stdin.readline

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

    for i in range(N):
        S, T, X = list(map(int, input().split()))
        heappush(event, [S-X-0.5, 0, X])
        heappush(event, [T-X-0.5, 1, X])

    for i in range(Q): heappush(event, [int(input()), 2, 0])

    d = []

    while event:
        _, m, x = heappop(event)

        if m == 0: insort_left(d, x)        
        elif m == 1: d.pop(bisect_left(d, x))
        else:
            if d: print(d[0])
            else: print(-1)
            
            Q -= 1
            if Q == 0: break
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#13:12
n,q = map(int,input().split())
import heapq
event = []
for _ in range(n):
  s,t,x = map(int,input().split())
  heapq.heappush(event,(s-x,t-x,x))
t = 0
now = []
for _ in range(q):
  d = int(input())
  if event:
    while event[0][0] <= d:
      tmp = heapq.heappop(event)
      heapq.heappush(now,(tmp[2],tmp[1]))
      if not event:
        break
  if now:
    while now[0][1] <= d:
      heapq.heappop(now)
      if not now:
        print(-1)
        break
    else:
      print(now[0][0])
  else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#13:12
import sys
input = sys.stdin.readline
n,q = map(int,input().split())
event = []
for _ in range(n):
  s,t,x = map(int,input().split())
  event.append((s-x,1,x))
  event.append((t-x,0,x))
event.sort()
t = 0
now = set()
for _ in range(q):
  d = int(input())
  if t == 2*n:
    print(-1)
    continue
  while event[t][0] <= d:
    if event[t][1] == 1:
      now.add(event[t][2])
    else:
      now.remove(event[t][2])
    t += 1
    if t == 2*n:
      break
  try:
    print(min(now))
  except:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#13:12
n,q = map(int,input().split())
import heapq
import sys
input = sys.stdin.readline
event = []
for _ in range(n):
  s,t,x = map(int,input().split())
  heapq.heappush(event,[s-x,t-x,x])
t = 0
now = []
for _ in range(q):
  d = int(input())
  if event:
    while event[0][0] <= d:
      tmp = heapq.heappop(event)
      heapq.heappush(now,[tmp[2],tmp[1]])
      if not event:
        break
  if now:
    while now[0][1] <= d:
      heapq.heappop(now)
      if not now:
        print(-1)
        break
    else:
      print(now[0][0])
  else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#13:12
n,q = map(int,input().split())
import heapq
event = []
for _ in range(n):
  s,t,x = map(int,input().split())
  heapq.heappush(event,[s-x,t-x,x])
t = 0
now = []
for _ in range(q):
  d = int(input())
  if event:
    while event[0][0] <= d:
      tmp = heapq.heappop(event)
      heapq.heappush(now,[tmp[2],tmp[1]])
      if not event:
        break
  if now:
    while now[0][1] <= d:
      heapq.heappop(now)
      if not now:
        print(-1)
        break
    else:
      print(now[0][0])
  else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#13:12
import sys
input = sys.stdin.readline
n,q = map(int,input().split())
event = []
for _ in range(n):
  s,t,x = map(int,input().split())
  event.append([s-x,1,x])
  event.append([t-x,0,x])
event.sort()
t = 0
now = set()
for _ in range(q):
  d = int(input())
  if t == 2*n:
    print(-1)
    continue
  while event[t][0] <= d:
    if event[t][1] == 1:
      now.add(event[t][2])
    else:
      now.remove(event[t][2])
    t += 1
    if t == 2*n:
      break
  try:
    print(min(now))
  except:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#13:12
n,q = map(int,input().split())
event = []
for _ in range(n):
  s,t,x = map(int,input().split())
  event.append([s-x,1,x])
  event.append([t-x,0,x])
event.sort()
t = 0
now = set()
for _ in range(q):
  d = int(input())
  if t == 2*n:
    print(-1)
    continue
  while event[t][0] <= d:
    if event[t][1] == 1:
      now.add(event[t][2])
    else:
      now.remove(event[t][2])
    t += 1
    if t == 2*n:
      break
  try:
    print(min(now))
  except:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
n, q = list(map(int, input().split()))
eventList = []

for i in range(n):
    stop = list(map(int, input().split()))
    eventList.append([stop[0] - stop[2], 1, stop[2]])
    eventList.append([stop[1] - stop[2], -1, stop[2]])


for i in range(q):
    departure = int(input())
    eventList.append([departure, 0, i])

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

ans = []
stopArea = []
for event in eventList:
    if event[1] == 1:
        stopArea.append(event[2])
    elif event[1] == -1:
        stopArea.remove(event[2])
    else:
        if len(stopArea) == 0:
            ans.append(-1)
        else:
            ans.append(min(stopArea))

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
n, q = list(map(int, input().split()))
stopList = []
departureList = []

for i in range(n):
    stop = list(map(int, input().split()))
    stopList.append(stop)

for i in range(q):
    departure = int(input())
    departureList.append(departure)

stopList.sort(key=lambda x:x[2])

distanceList=[ -1 for i in range(q) ]
for idx, d in enumerate(departureList):
    for s in stopList:
        if s[0]<= d+s[2] and d+s[2]<s[1]:
            distanceList[idx]=s[2]
            break

for val in distanceList:
    print(val)

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))  # 通行止め削除

    for i in range(Q):
        d = int(input())
        events.append((d, 2, 0))  # チェックイベント

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

    i = 0
    closing = set()
    hq = []  # 最小値を高速に入手するため
    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)

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

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

        i += 1


if __name__ == '__main__':
    main()

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))  # 通行止め削除

    for i in range(Q):
        d = int(input())
        events.append((d, 2, 0))

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

    i = 0
    closing = set()
    hq = []  # 最小値を高速に入手するため
    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)

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

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

        i += 1


if __name__ == '__main__':
    main()

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:
from heapq import heappush, heappop
N, Q = map(int, input().split())
ls = []
for i in range(N):
  s, t, x = map(int, input().split())
  ls += [(s-x,1,x)]
  ls += [(t-x,0,x)]
for i in range(Q):
  d = int(input())
  ls += [(d,2,i)]
ls.sort()
se = set()
q = []
for a,b,c in ls:
  if b==1:
    se.add(c)
    heappush(q,c)
  elif b==0:
    se.remove(c)
  else:
    while q and q[0] not in se:
      heappop(q)
    ans = q[0] if q else -1
    print(ans)