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):
N , Q = map(int,input().split())

D = [0]*Q
Input = []
length = [-1]*Q

for i in range(N):
    Input.append(list(map(int,input().split())))


dist = lambda A : A[2]
Input.sort(key=dist)

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


time = lambda A : A[1]
D.sort(key=time)


skip = 0
for start in D:
    for j in range(N-skip):
        if(Input[j][1] <= start[1]): 
            Input.pop(j)
            skip += 1
            continue

        stopTime = Input[j][2] + start[1] 

        if(stopTime >= Input[j][0] - 0.5 and stopTime <= Input[j][1] - 0.5): 
            length[start[0]] = Input[j][2]
            break

for i in range(Q):
    print(length[i])


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

D = [0]*Q
Input = []
length = [-1]*Q

for i in range(N):
    Input.append(list(map(int,input().split())))


dist = lambda A : A[2]
Input.sort(key=dist)

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


time = lambda A : A[1]
D.sort(key=time)


skip = 0
for start in D:
    for j in range(N):
        if(Input[j][1] <= start[1]): 
            Input.pop(j)
            continue

        stopTime = Input[j][2] + start[1] 

        if(stopTime >= Input[j][0] - 0.5 and stopTime <= Input[j][1] - 0.5): 
            length[start[0]] = Input[j][2]
            break

for i in range(Q):
    print(length[i])


import sys
input = sys.stdin.readline

class MinSegTree:
    
    def __init__(self, size):
        self.size = 1 << (size.bit_length())  
        self.data = [INF] * (2 * self.size - 1)

    def build(self, rawData):
        self.data[self.size - 1: self.size - 1 + len(rawData)] = rawData
        for i in range(self.size - 1)[:: -1]:
            self.data[i] = min(self.data[2 * i + 1], self.data[2 * i + 2])

    def update(self, index, value):
        index += self.size - 1
        self.data[index] = value
        while index >= 0:
            index = (index - 1) // 2
            self.data[index] = min(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):
        L = left + self.size
        R = right + self.size
        ret = INF
        while L < R:
            if R & 1:
                R -= 1
                ret = min(ret, self.data[R - 1])
            if L & 1:
                ret = min(ret, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N, Q = map(int, input().split())
INF = float('inf')

events = []
for i in range(N):
    S, T, X = map(int, input().split())
    events.append((S - X, True, i, X))
    events.append((T - X, False, i, X))
events.sort()

tree = MinSegTree(N)

D = [int(input()) for _ in range(Q)]
M = len(events)
now = 0
ans = []
for d in D:
    while now < M and events[now][0] <= d:
        _, isStart, i, x = events[now]
        if isStart:
            tree.update(i, x)
        else:
            tree.update(i, INF)
        now += 1
    print(tree.data[0])


from heapq import heappush, heappop
import sys
input = sys.stdin.buffer.readline

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

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

D = [int(input()) for _ in range(Q)]

E.sort(key=lambda a: a[1], reverse=True)

ans = []
que = [(10**18, -1)]
V = set()
for d in D:
    while E and E[-1][1] <= d:
        f, _, x, i = E.pop()
        if f == 0:
            V.add(i)
        else:
            heappush(que, (x, i))
    while que[0][1] in V:
        heappop(que)
    ans.append(que[0][0])

ans = [a if a < 10**18 else -1 for a in ans]
print(*ans, sep='\n')


Verdicts: Runtime Error

Runtime Error

Wrong Answer

Accepted