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
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        XST.append(LI())
    D = []
    for _ in range(Q):
        D.append(II())
    ans = [INF] * len(D)
    for x, s, t in XST:
        s0 = bisect_left(D, s - x)
        t0 = bisect_left(D, t - x)
        for i in range(s0, t0):
            ans[i] = min(ans[i], x)
    for y in ans:
        print(-1 if y == INF else y)
    return

main()


import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, Q = LI()
    events = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        events.append([s, x])
        events.append([t, -x])
    for _ in range(Q):
        d = II()
        events.append([d, INF])
    events.sort()
    dst = {}
    for t, x in events:
        if x == INF: 
            y = min(dst) if len(dst) else -1
            print(y)
        elif x > 0: # add
            dst.add(x)
        else: 
            dst.remove(-x)
    return

main()

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

def main():
    N, Q = LI()
    events = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        events.append([s, x])
        events.append([t, -x])
    for _ in range(Q):
        d = II()
        events.append([d, INF])
    events.sort()
    dst = {}
    for t, x in events:
        if x == INF: 
            y = min(dst) if dst else -1
            print(y)
        elif x > 0: # add
            dst.add(x)
        else: 
            dst.remove(-x)
    return

main()

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect

def main():
    N, Q = LI()
    XST = []
    ts = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        XST.append([x, s, t])
        ts.append(s)
        ts.append(t)
    ts.sort()
    ts.append(INF)
    D = []
    for _ in range(Q):
        D.append(II())
    xs = [INF] * (N * 2 + 1)
    XST.sort(reverse=True)
    for x, s, t in XST:
        s0 = bisect(ts, s)
        t0 = bisect(ts, t)
        for i in range(s0, t0):
            xs[i] = x
    for d in D:
        y = bisect(ts, d)
        y = xs[y]
        if y == INF:
            y = -1
        print(y)
        ts = ts[y:]
        xs = xs[y:]
    return

main()

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LLI(): return [int(x) for x in sys.stdin.readlines()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        XST.append([x, s, t])
    XST.sort()
    D = LLI()
    ans = [-1] * Q
    nexts = [-1] * Q
    for x, s, t in XST:
        i = bisect_left(D, s - x)
        end = bisect_left(D, t - x)
        to = end
        while to < Q and nexts[to] != -1:
            to = nexts[to]
        while i < end:
            if nexts[i] == -1:
                ans[i] = x
                nexts[i] = to
                i += 1
            else:
                i = nexts[i]
    for y in ans:
        print(y)
    return

main()


Verdicts: Wrong Answer

Runtime Error

Runtime Error

Runtime Error

Accepted