Problem: 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.

Submission attempts (in order):
import sys
import bisect
import heapq
sys.setrecursionlimit(10 ** 7)

# TLE

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

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

ans = [-1] * Q

EVENT.sort()

# print(EVENT)

STOP = []
for t, op, x in EVENT:
    if op == 2 and STOP:
        ans[x] = STOP[0]
    elif op == 0:
        heapq.heappush(STOP, x)
    elif op == 1:
        STOP.remove(x)


print("\n".join(map(str, ans)))


import sys
import bisect
import heapq
sys.setrecursionlimit(10 ** 7)

# TLE

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

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

ans = [-1] * Q

EVENT.sort()

STOP = []
for t, op, x in EVENT:
    if op == 0 and STOP:
        ans[x] = STOP[0]
    elif op == 1:
        heapq.heappush(STOP, x)
    elif op == -1:
        STOP.remove(x)


print("\n".join(map(str, ans)))


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))


import sys
import bisect
import heapq
sys.setrecursionlimit(10 ** 7)

# TLE

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

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

ans = [-1] * Q

EVENT.sort()

# print(EVENT)

STOP = set()
for t, op, x in EVENT:
    if op == 2 and STOP:
        ans[x] = min(list(STOP))
    elif op == 0:
        #heapq.heappush(STOP, x)
        STOP.add(x)
    elif op == 1:
        if x in STOP:
            STOP.remove(x)
        # heapq.heapify(STOP)


print("\n".join(map(str, ans)))


import sys
#import numpy as np
import bisect
sys.setrecursionlimit(10 ** 7)

# TLE
# PyPy3 (2.4.0) 2112 ms

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 = [-1] * Q

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

for s, t, x in STX:
    if len(PEOPLE) == 0:
        break

    i = bisect.bisect_left(PEOPLE, s - x)
    j = bisect.bisect_left(PEOPLE, t - x)

    if i == j:
        continue

    use = [PEOPLE[x] for x in range(i, j)]

    for k in use:
        if ans[k] == -1:
            ans[k] = x

    del PEOPLE[i:j]


print("\n".join(map(str, ans)))


from heapq import heappush, heappop
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, Q = map(int, readline().split())
STX = [[int(x) for x in readline().split()] for _ in range(N)]
EVENT = []
for s, t, x in STX:
    EVENT.append((s-x, 1, x))
    EVENT.append((t-x, 0, x))

for i in range(Q):
    d = int(readline())
    EVENT.append((d, 2, i))

ans = [-1] * Q

EVENT.sort()


STOP = set()
h = []
for t, op, x in EVENT:
    if op == 2 and STOP:
        while h and h[0] not in STOP:
            heappop(h)
        ans[x] = h[0]
    elif op == 1:
        STOP.add(x)
        heappush(h, x)
    elif op == 0:
        STOP.remove(x)

print("\n".join(map(str, ans)))


Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Accepted