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 numpy as np
import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    X = []
    for _ in range(N):
        start, end, pos = map(int, input().split())
        X.append((pos, start, end))

    X = sorted(X, key=lambda x: x[0])
    positions = np.zeros(N+1, dtype=np.int)
    starts = np.zeros(N+1, dtype=np.int)
    ends = np.zeros(N+1, dtype=np.int)
    for i, (pos, start, end) in enumerate(X):
        positions[i] = pos
        starts[i] = start
        ends[i] = end

    positions[N] = -1
    starts[N] = -2
    ends[N] = 10**9

    for _ in range(Q):
        d = int(input())

        before = (positions + d) > starts
        after = (positions + d) <= ends
        check = before * after

        print(positions[check][0])


if __name__ == '__main__':
    main()


import numpy as np
import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    X = []
    for _ in range(N):
        start, end, pos = map(int, input().split())
        X.append((pos, start, end))

    X = sorted(X, key=lambda x: x[0])
    positions = np.zeros(N+1, dtype=np.int)
    starts = np.zeros(N+1, dtype=np.int)
    ends = np.zeros(N+1, dtype=np.int)
    for i, (pos, start, end) in enumerate(X):
        positions[i] = pos
        starts[i] = start
        ends[i] = end

    positions[N] = -1
    starts[N] = -1
    ends[N] = 10**9

    for _ in range(Q):
        d = int(input())

        before = (positions + d) >= starts
        after = (positions + d) < ends
        check = before * after

        print(positions[check][0])


if __name__ == '__main__':
    main()


import numpy as np
import sys
from bisect import bisect_left

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    closure = []
    for _ in range(N):
        start, end, pos = map(int, input().split())
        closure.append((pos, start, end))

    closure.sort()

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

    ans = np.full(Q, 10**9, dtype=np.int)
    mask = np.full(Q, -1, dtype=np.int)
    for pos, start, end in closure:
        left = bisect_left(D, start - pos)
        right = bisect_left(D, end - pos)

        ans[left:right] = np.minimum(ans[left:right], pos)
        mask[left:right] = pos

    ans = np.minimum(ans, mask)

    return ans


if __name__ == '__main__':
    print(*main(), sep='\n')




import sys
from bisect import bisect_left

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    closure = []
    for _ in range(N):
        start, end, pos = map(int, input().split())
        closure.append((pos, start, end))

    closure.sort()

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

    ans = [-1] * Q
    skip = [-1] * Q
    for pos, start, end in closure:
        left = bisect_left(D, start - pos)
        right = bisect_left(D, end - pos)

        while left < right:
            if skip[left] == -1:
                ans[left] = pos
                skip[left] = right
                left += 1
            else:
                left = skip[left]

    return ans


if __name__ == '__main__':
    print(*main(), sep='\n')


Verdicts: Wrong Answer

Time Limit Exceeded

Time Limit Exceeded

Accepted