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
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    ans = [-1] * q
    for i in range(q):
        d = int(input())
        ds.append(d)

    for x, s, t in xst:
        st = bisect_left(ds, s)
        for i in range(st, q):
            if d[i] >= t:
                break
            if ans[i] == -1:
                ans[i] = x

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

n, q = map(int, input().split())
f(n, q)


import sys
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    for i in range(q):
        d = int(input())
        ds.append(d)

    ans = [-1] * q
    jump = [-1] * q

    for x, s, t in xst:
        i = bisect_left(ds, s)
        fi = bisect_left(ds, t)
        while i < fi:
            if jump[i] != -1:
                i = jump[i]
            ans[i] = x
            jump[i] = fi
            i += 1

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

n, q = map(int, input().split())
f(n, q)



from heapq import *

n, q = map(int, input().split())
events = []
heapify(events)
ans = [-1] * q
koji = set()
for _ in range(n):
    s, t, x = map(int, input().split())
    heappush(events, [s - x - 0.3, x, 1])
    heappush(events, [t - x - 0.7, x, 2])
for i in range(q):
    d = int(input())
    heappush(events, [d, i, 3])
for _ in range(n * 2 + q):
    j, h, s = heappop(events)
    if s == 1:
        koji.add(h)
    elif s == 2:
        koji.remove(h)
    else:
        if koji:
            ans[h] = min(koji)
print(ans)



import sys
from heapq import *
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    dis=[]
    ans = [-1] * q
    for i in range(q):
        d = int(input())
        heappush(ds,d)
        heappush(dis, [d, i])


    for x, s, t in xst:
        i=bisect_left(ds,s)
        nd=len(ds)
        while i<nd:
            if ds[i]<t:
                ai=dis[i][1]
                ans[ai]=x
                del ds[i]
                del dis[i]
                nd-=1
            else:
                break

    print(ans)


n, q = map(int, input().split())
f(n, q)


def f(n, q):
    dp=[-1]*(10**9+1)
    for _ in range(n):
        s, t, x = map(int, input().split())
        for i in range(s-x,t-x):
            if dp[i]>x or dp[i]==-1:
                dp[i]=x
    for _ in range(q):
        d = int(input())
        print(dp[d])

n, q = map(int, input().split())
f(n, q)


import sys
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    for i in range(q):
        d = int(input())
        ds.append(d)

    ans = [-1] * q
    jump = [-1] * q

    for x, s, t in xst:
        i = bisect_left(ds, s)
        fi = bisect_left(ds, t)
        while i < fi:
            if jump[i] != -1:
                i = jump[i]
            else:
                ans[i] = x
                jump[i] = fi
                i += 1

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

n, q = map(int, input().split())
f(n, q)


Verdicts: Runtime Error

Runtime Error

Wrong Answer

Wrong Answer

Runtime Error

Accepted