Problem:


Score : 500 points

Problem Statement

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.

Constraints

All values in input are integers.

1 \leq N, Q \leq 2 \times 10^5

0 \leq S_i < T_i \leq 10^9

1 \leq X_i \leq 10^9

0 \leq D_1 < D_2 < ... < D_Q \leq 10^9

If i \neq j and X_i = X_j, the intervals [S_i, T_i) and [S_j, T_j) do not overlap.

Input

Input is given from Standard Input in the following format:

N Q
S_1 T_1 X_1
:
S_N T_N X_N
D_1
:
D_Q

Output

Print Q lines. The i-th line should contain the distance the i-th person will walk or -1 if that person walks forever.

Sample Input 1

4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8

Sample Output 1

2
2
10
-1
13
-1

The first person starts coordinate 0 at time 0 and stops walking at coordinate 2 when reaching a point blocked by the first roadwork at time 2.

The second person starts coordinate 0 at time 1 and reaches coordinate 2 at time 3. The first roadwork has ended, but the fourth roadwork has begun, so this person also stops walking at coordinate 2.

The fourth and sixth persons encounter no roadworks while walking, so they walk forever. The output for these cases is -1.



Sample input:
4 6
1 3 2
7 13 10
18 20 13
3 4 2
0
1
2
3
5
8


Sample output:
2
2
10
-1
13
-1

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**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 sys.stdin.readline().strip()
MOD = 10 ** 9 + 7


def main(): 
    N, Q = LI()
    STX = []
    for _ in range(N):
        STX.append(LI())
    D = []
    for _ in range(Q):
        D.append(II())

    # セグメント木
    # N: 処理する区間の長さ
    N0 = 2**(N-1).bit_length()
    INF = 2**31-1
    data = [INF]*(2*N0)
    # a_k の値を x に更新
    def update(k, x):
        k += N0-1
        data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            data[k] = min(data[2*k+1], data[2*k+2])
    # 区間[l, r)の最小値
    def query(l, r):
        L = l + N0; R = r + N0
        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, data[R-1])

            if L & 1:
                s = min(s, data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

    events = []
    construction_number = 0
    for s, t, x in STX:
        events.append((s - x, x, True, construction_number))  # S-X, X, add_flag
        events.append((t - x, x, False, construction_number))  # T-X, X, add_flag
        construction_number += 1

    events.sort()  # O(N log N)
    # D is already sorted by input.

    d = D.pop(0)
    d_num = 0
    ans = [-1] * Q
    for time, x, add_flag, construction_number in events:
        while d < time:
            min_ = query(0, N)
            ans[d_num] = -1 if min_==INF else min_
            d = D.pop(0)
            d_num += 1
        if add_flag:
            update(construction_number, x)
        else:
            update(construction_number, INF)

    for i in ans: print(i)

main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**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 sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, Q = LI()
    STX = []
    for _ in range(N):
        STX.append(LI())
    D = []
    for _ in range(Q):
        D.append(II())

    events = []
    for s, t, x in STX:
        events.append((s - x, x, True))  # S-X, X, add_flag
        events.append((t - x, x, False))  # T-X, X, add_flag

    events.sort()  # O(N log N)
    # D is already sorted by input.

    d = D.pop(0)
    d_num = 0
    ans = [-1] * Q
    blocked = set()
    import heapq
    hq = []
    for time, x, add_flag in events:
        while d < time:
            if not blocked:
                ans[d_num] = -1
                hq = []
                d = D.pop(0)
                d_num += 1
                continue
            else:
                while True:
                    if hq[0] in blocked:
                        ans[d_num] = hq[0]
                        d = D.pop(0)
                        d_num += 1
                        break
                    else:
                        heapq.heappop(hq)
                        continue
        if add_flag:
            blocked.add(x)
            heapq.heappush(hq, x)
        else:
            blocked.remove(x)

    for i in ans: print(i)

main()

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())

list_a = []
list_b = []
list_dist = []

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

for j in range(Q):
  list_b.append(int(input()))

list_a.sort(key=lambda x:(x[2],x[0],x[1]))

for b in list_b:
  dist = 0
  time = b
  stop_flag = 0
  for a in list_a:
    time = time + a[2] - dist
    dist = a[2]
    if time > a[0]-0.5 and time < a[1]-0.5:
      stop_flag = 1
      break
  if stop_flag == 0:
    list_dist.append(-1)
  else:
    list_dist.append(dist)

for dist in list_dist:
  pritn(dist)

Submission status: Runtime Error

Solution code:
 N,Q = map(int,input().split())
event = []
for i in range(N):
    s,t,x = map(int,input().split())
    event.append((s-x,x,1))
    event.append((t-x,x,-1))

s = set()

event.sort()
event.reverse()


for i in range(Q):
    D = int(input())
    f = False
    while event:
        t,x,e = event.pop()
        if D < t:
            f = True
            break
        if e == 1:
            s.add(x)
        else:
            s.remove(x)
    if len(s)==0:
        print(-1)
    else:
        print(min(s))
    if f:
        if e == 1:
            s.add(x)
        else:
            s.remove(x)

Submission status: Runtime Error

Solution code:
s = set()

event.sort()
event.reverse()


for i in range(Q):
    D = int(input())
    f = False
    while event:
        t,x,e = event.pop()
        if D < t:
            f = True
            break
        if e == 1:
            s.add(x)
        else:
            s.remove(x)
    if len(s)==0:
        print(-1)
    else:
        print(min(s))
    if f:
        if e == 1:
            s.add(x)
        else:
            s.remove(x)

Submission status: Runtime Error

Solution code:
#Dが (S-X) < D < (T-X) のときに地点Xでぶつかる
import bisect
from collections import OrderedDict
N, Q = map(int, input().split())

# 工事状況
L = []
for i in range(N):
    s, t, x = map(int, input().split())
    L.append((s-x, t-x, x))
# 工事状況を近い順にソート
L = sorted(L, key=lambda p:p[2])

# 人
D_ = []
for i in range(Q):
    D_.append((int(input()), i))
# 時刻順にソート
D_ = sorted(D_)
D = D_

# 距離を順次格納:
DD = [-1] * len(D)

# 工事を近い順に検索
# つまり、最初にヒットした工事でその人は止まる
for l in L:
    # その工事で止まる人を探索
    left = bisect.bisect_left(D, (l[0], 0))
    
    i = left
    while True:
        if D[i] > (l[1], -1):
            break

        d = D[i]
        DD[d[1]] = l[2]
        i += 1

    right = i
    # もう考慮しなくてよい人を取り除く
    del D[left:right]

# 出力
for d in DD:
    print(d)

Submission status: Runtime Error

Solution code:
#Dが (S-X) < D < (T-X) のときに地点Xでぶつかる
import bisect
from collections import OrderedDict
N, Q = map(int, input().split())

# 工事状況
L = []
for i in range(N):
    s, t, x = map(int, input().split())
    L.append((s-x, t-x, x))
# 工事状況を近い順にソート
L = sorted(L, key=lambda p:p[2])

# 人
D_ = []
for i in range(Q):
    D_.append((int(input()), i))
# 時刻順にソート
D_ = sorted(D_)
D = D_

# 距離を順次格納:
DD = [-1] * len(D)

# 工事を近い順に検索
# つまり、最初にヒットした工事でその人は止まる
for l in L:
    # その工事で止まる人を探索
    left = bisect.bisect_left(D, (l[0], 0))
    
    i, d = left, D[left]
    while d[0] < l[1]:
        DD[d[1]] = l[2]
        i += 1
        d = D[i]
    right = i
    # もう考慮しなくてよい人を取り除く
    del D[left:right]

# 出力
for d in DD:
    print(d)

Submission status: Runtime Error

Solution code:
import sys
from operator import itemgetter


scan = sys.stdin.readline


def main():
    n, q = map(int, scan().rstrip().split())
    schedules = [tuple(map(int, scan().rstrip().split())) for _ in range(n)]
    d = [int(scan().rstrip()) for _ in range(q)]

    pos = [[0, False] for _ in range(q)]

    schedules.sort(key=itemgetter(0))
    construction = []
    i = 0

    # caution
    for time in range(schedules[n - 1][1] + 1):
        while len(schedules) > i and schedules[i][0] > time:
            construction.append((schedules[i][1], schedules[i][2]))
            i += 1

        for j in range(len(construction)):
            if construction[j][0] <= time:
                construction.remove(j)

        for person in range(q):
            if d[person] < time and not pos[person][1]:
                pos[person][0] += 1

                for j in range(len(construction)):
                    if pos[person][0] == construction[j][1]:
                        pos[person][1] = True

    for position, has_stopped in pos:
        if has_stopped:
            print(position)
        else:
            print(-1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
from operator import itemgetter


scan = sys.stdin.readline


def main():
    n, q = map(int, scan().rstrip().split())
    schedules = [tuple(map(int, scan().rstrip().split())) for _ in range(n)]
    d = [int(scan().rstrip()) for _ in range(q)]

    pos = [[0, False] for _ in range(q)]

    schedules.sort(key=itemgetter(0))
    construction = []
    i = 0

    # caution
    for time in range(schedules[n - 1][1] + 1):
        while schedules[i][0] > time:
            construction.append((schedules[i][1], schedules[i][2]))
            i += 1

        for j in range(len(construction)):
            if construction[j][0] <= time:
                construction.remove(j)

        for person in range(q):
            if d[person] < time and not pos[person][1]:
                pos[person][0] += 1
                
                for j in range(len(construction)):
                    if pos[person][0] == construction[j][1]:
                        pos[person][1] = True

    for position, has_stopped in pos:
        if has_stopped:
            print(position)
        else:
            print(-1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,Q = map(int,input().split())
event = []
for i in range(N):
    s,t,x = map(int,input().split())
    event.append((s-x,x,1))
    event.append((t-x,x,-1))

s = set()

event.sort()

for i in range(Q):
    D = int(input())
    while event:
        t,x,f = event.pop(0)
        if D < t:
            break
        if f == 1:
            s.add(x)
        else:
            s.remove(x)
    if len(s)==0:
        print(-1)
    else:
        print(min(s))
    if D < t:
        if f == 1:
            s.add(x)
        else:
            s.remove(x)

Submission status: Runtime Error

Solution code:
#ref : https://atcoder.jp/contests/abc128/submissions/5694292
#工事を座標順に処理，工事にぶつかる人をにぶたん
#すでに更新済みだったら更新しない．-> jumpで管理
from bisect import bisect_left
N, Q = map(int, input().split())
consts = []
for _ in range(N):
    s,t,x = map(int, input().split())
    consts.append((x,s,t))
const.sort()
D=[int(input()) for _ in range(Q)]
ans=[-1]*Q
jump=[-1]*Q
for x,s,t in consts:
    left=bisect_left(D,s-x)
    right=bisect_left(D,t-x)
    while left<right:
        if jump[left]==-1:
            ans[left]=x
            jump[left]=right
            left += 1
        else:
            left=jump[left]
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
N, Q = map(int, input().split())
consts = []
for _ in range(N):
    s,t,x = map(int, input().split())
    consts.append((x,s,t))
const.sort()
D=[int(input()) for _ in range(Q)]
ans=[-1]*Q
jump=[-1]*Q
for x,s,t in consts:
     left=bisect_left(D,s-x)
     right=bisect_left(D,t-x)
     while left<right:
         if jump[left]==-1:
             ans[left]=x
             jump[left]=right
             left += 1
         else:
             left=jump[left]
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
import bisect
import copy
N, Q = map(int, input().split())
events = []
for i in range(N):
    s,t,x = map(int, input().split())
    events.append([s-x, 1, x])
    events.append([t-x, -1, x])
events.sort()
events=np.array(events)
sets = set()
prev = 0
for _ in range(Q):
    d = int(input())
    index = bisect.bisect_right(events[:,0], d)
    for i in range(prev, index):
        t, pm, x = events[i]
        if pm == 1:
            sets.add(x)
        if pm == -1:
            sets.remove(x)
    prev=copy.copy(index)
    if len(sets)==0:
        print(-1)
    else:
        print(min(sets))

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())
 
def ss_raw():
    return input().split()
 
def ints_raw():
    return tuple(map(int, ss_raw()))


def main():
    N ,Q = ints_raw()
    origST = []

    for idx  in range(N):
        S,T,X = ints_raw()
        origST.append([S-X,T-X,X])
    Ds = [int(input()) for _ in range(Q)]

    origST.sort()
    stidx = 0
    cur_set = []
    for d in Ds:

        while stidx < len(origST):
            st = origST[stidx]
            if st[0] > d:
                break
            heappush(cur_set,(st[2],st[1]))
            stidx+=1
        while cur_set and cur_set[0][1] <=d:
            heappop(cur_set)
        if cur_set:
            print(-1)
        else:
            print(cur_set[0][0])
main()

Submission status: Runtime Error

Solution code:
def BinarySearchLowerBound(_arr, _ele): # arr is strictly increasing
    low_ind = 0
    up_ind = len(_arr) - 1
    if _arr[low_ind] >= _ele:
        return low_ind
    if _arr[up_ind] <= _ele:
        return up_ind
    found = None
    while (up_ind - low_ind) > 1:
        mid = (up_ind + low_ind) / 2
        if _arr[mid] < _ele:
            low_ind = mid
        elif _arr[mid] > _ele:
            up_ind = mid
        elif _arr[mid] == _ele:
            found = mid
            break
    if found is not None:
        cnt = found
    else:
        cnt = up_ind
    return cnt

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        it = BinarySearchLowerBound(D, (Li, -1))
        while it < len(D):
            if D[it][0]>= Ri:
                break
            ans[D[it][1]] = Xi
            D.pop(it)
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
def BinarySearchLowerBound(_arr, _ele): # arr is strictly increasing
    low_ind = 0
    up_ind = len(_arr) - 1
    found = None
    if _arr[low_ind] >= _ele:
        return low_ind
    while (up_ind - low_ind) > 1:
        mid = (up_ind + low_ind) / 2
        if _arr[mid] < _ele:
            low_ind = mid
        elif _arr[mid] > _ele:
            up_ind = mid
        elif _arr[mid] == _ele:
            found = mid
            break
    if found is not None:
        cnt = found
    else:
        cnt = up_ind
    return cnt

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        it = BinarySearchLowerBound(D, (Li, -1))
        while it < len(D):
            if D[it][0] >= Ri:
                break
            ans[D[it][1]] = Xi
            D.pop(it)
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
def BinarySearchLowerBound(_arr, _ele): # arr is strictly increasing
    low_ind = 0
    up_ind = len(_arr) - 1
    found = None
    if _arr[low_ind] >= _ele:
        return low_ind
    while (up_ind - low_ind) > 1:
        mid = (up_ind + low_ind) / 2
        if _arr[mid] < _ele:
            low_ind = mid
        elif _arr[mid] > _ele:
            up_ind = mid
        elif _arr[mid] == _ele:
            found = mid
            break
    if found is not None:
        cnt = found
    else:
        cnt = up_ind
    return cnt

def solve():
    N, Q = [int(_) for _ in raw_input().split()]
    STX = []
    for i in range(N):
        Si, Ti, Xi = [int(_) for _ in raw_input().split()]
        STX.append((Si - Xi, Ti - Xi, Xi))
    D = []
    for i in range(Q):
        D.append((int(raw_input()), i))
    STX.sort(key = lambda x:x[2])
    # D have already been sorted based on settings on problem
    ans = [-1] * Q
    for i in range(N):
        Li, Ri, Xi = STX[i]
        it = BinarySearchLowerBound(D, (Li, -1))
        while it < len(D):
            if D[it][0] >= Ri:
                break
            ans[D[it][1]] = Xi
            D.pop(it)
            print "after: " + str(D) + ", " + str(it)
    for i in range(Q):
        print ans[i]

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import bisect, queue
N, Q = map(int,input().split())
C = [list(map(int,input().split())) for k in range(N)]
D = [int(input()) for k in range(Q)]

E = []
for c in C:
    s, e, x = c[0], c[1], c[2]
    E.append([x,s-x,e-x])
E.sort()

ans = queue.Queue()
U = [0 for k in range(Q)]
for e in E:
    t = bisect.bisect_left(D,e[1])
    while t < Q:
        while D[t] < e[2] and U[t] == 1:
            t += 1
        if D[t] < e[2] and U[t] == 0:
            ans.put(e[0])
            U[t] = 1
            t += 1
        else:
            break

for k in range(Q):
    if U[k] == 1:
        print(ans.get())
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
from operator import itemgetter

input = sys.stdin.readline

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1] * Q
jump = [-1] * Q
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    while left < right:
        if time[left] == -1:
            time[left] = x
            jump[left] = right
            left += 1
        else:
            left = jump[left]

for t in time:
    print(t)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, Q = map(int, input().split())
S = [0] * N
T = [0] * N
X = [0] * N
D = [0] * Q
event = []
working = []

for i in range(N):
	S[i], T[i], X[i] = map(int, input().split())
	event.append((S[i] - X[i], 1, X[i]))
	event.append((T[i] - X[i], -1, X[i]))
	
for i in range(Q):
	D[i] = int(input())
	
event.sort()
j = 0

for i in range(len(event)):		
	while event[i][0] > D[j] and j < Q:
		if len(working) > 0:
			print(min(working))
		else:
			print(-1)
		j += 1
	
	if event[i][1] == 1:
		working.append(event[i][2])
	else:
		working.remove(event[i][2])

while j < Q:
	print(-1)
	j += 1

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, Q = map(int, input().split())
S = [0] * N
T = [0] * N
X = [0] * N
D = [0] * Q
event = []
working = []
for i in range(N):
	S[i], T[i], X[i] = map(int, input().split())
	event.append((S[i] - X[i], 1, X[i]))
	event.append((T[i] - X[i], -1, X[i]))
	
for i in range(Q):
	D[i] = int(input())
	
event.sort()
j = 0
for i in range(len(event)):		
	while event[i][0] > D[j] and j < Q:
		if len(working) > 0:
			print(working[0])
		else:
			print(-1)
		j += 1
	
	if event[i][1] == 1:
		working.append(event[i][2])
	else:
		working.remove(event[i][2])

while j < Q:
	print(-1)
	j += 1

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, Q = map(int, input().split())
S = [0] * N
T = [0] * N
X = [0] * N
D = [0] * Q
event = []
working = []
for i in range(N):
	S[i], T[i], X[i] = map(int, input().split())
	event.append((S[i] - X[i], 1, X[i]))
	event.append((T[i] - X[i], -1, X[i]))
	
for i in range(Q):
	D[i] = int(input())
	
event.sort()
j = 0
for i in range(len(event)):		
	while event[i][0] > D[j] and j < Q:
		if len(working) > 0:
			print(min(working))
		else:
			print(-1)
		j += 1
	
	if event[i][1] == 1:
		working.append(event[i][2])
	else:
		working.remove(event[i][2])

while j < Q:
	print(-1)
	j += 1

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, Q = map(int, input().split())
S = [0] * N
T = [0] * N
X = [0] * N
D = [0] * Q
event = []
working = []
for i in range(N):
	S[i], T[i], X[i] = map(int, input().split())
	event.append((S[i] - X[i], 1, X[i]))
	event.append((T[i] - X[i], -1, X[i]))
	
for i in range(Q):
	D[i] = int(input())
	
event.sort()
j = 0
for i in range(len(event)):		
	while event[i][0] > D[j]:
		if len(working) > 0:
			print(min(working))
		else:
			print(-1)
		j += 1
	
	if event[i][1] == 1:
		working.append(event[i][2])
	else:
		working.remove(event[i][2])

while j < Q:
	print(-1)
	j += 1

Submission status: Runtime Error

Solution code:
import bisect
import collections

N, Q = map(int, input().split())
stoppedDict = collections.defaultdict(set)  # {d: x} dに出発すると、xで止まるという形式
for i in range(N):
    s, t, x = map(int, input().split())
    for j in range(s-x, t-x):
        stoppedDict[j].add(x)
#print(stoppedDict)


def solve(d):
    if len(stoppedDict[d]) != 0:
        return min(stoppedDict[d])
    else:
        return -1


for i in range(Q):
    d = int(input())
    print(solve(d))
import bisect
import collections

N, Q = map(int, input().split())
stoppedDict = collections.defaultdict(set)  # {d: x} dに出発すると、xで止まるという形式
for i in range(N):
    s, t, x = map(int, input().split())
    for j in range(s-x, t-x):
        stoppedDict[j].add(x)
#print(stoppedDict)


def solve(d):
    if len(stoppedDict[d]) != 0:
        return min(stoppedDict[d])
    else:
        return -1


for i in range(Q):
    d = int(input())
    print(solve(d))

Submission status: Runtime Error

Solution code:
import sys
from operator import itemgetter
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
E = [None]*2*N
for n in range(N):
	a,b,c = map(int,inputs().split())
	E[2*n] = (a - c, 1, c)
	E[2*n + 1] = (b - c, -1, c)
E.sort(key=itemgetter(0))
tuple(E)
mini = 1000000001
kouho = {1000000001}
my_add = kouho.add
my_discard = kouho.remove
q = 0
d = int(inputs())
flag = False
cont = False
for e in E:
	while(e[0] > d):
		if cont == True:
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		else:
			mini = min(kouho)
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		cont = True
		if q < Q-1:
			q = q + 1
			d = int(inputs())
		else:
			flag = True
			q = q + 1
			break
	if flag == True:
		break
	if e[1] == 1:
		my_add(e[2])
		if mini > e[2]:
			mini = e[2]
	elif e[1] == -1:
		my_discard(e[2])
		cont = False
for t in [None]*(Q-q):
	print(-1)

Submission status: Runtime Error

Solution code:
import sys
from operator import itemgetter
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
E = [None]*2*N
for n in range(N):
	a,b,c = map(int,inputs().split())
	E[2*n] = (a - c, 1, c)
	E[2*n + 1] = (b - c, -1, c)
E.sort(key=itemgetter(0))
tuple(E)
mini = 1000000001
kouho = {1000000001}
my_add = kouho.add
my_discard = kouho.remove
q = 0
d = int(inputs())
flag = False
cont = False
for e in E:
	while(e[0] > d):
		print(kouho)
		if cont == True:
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		else:
			mini = min(kouho)
			if mini < 1000000001:
				print(mini)
			else:
				print(-1)
		cont = True
		if q < Q-1:
			q = q + 1
			d = int(inputs())
		else:
			flag = True
			q = q + 1
			break
	if flag == True:
		break
	if e[1] == 1:
		my_add(e[2])
		if mini > e[2]:
			mini = e[2]
	elif e[1] == -1:
		my_discard(e[2])
		cont = False
for t in [None]*(Q-q):
	print(-1)

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
stop=[]
for i in range(n):
  a=list(map(int,input().split()))
  stop.append(a)
for i in range(q): 
  b=int(input())
  for j in range(n):
    flag=0
    
    if stop[i][0]<=stop[i][2]+b<stop[i][1]:
      print(stop[i][2])
      flag=1
      break
    if flag==0:
      print(-1)

Submission status: Runtime Error

Solution code:
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [None]*N
E = []
for n in range(N):
	V[n] = list(map(int,inputs().split()))
	V[n][0] -= V[n][2]
	V[n][1] -= V[n][2]
	E.append([V[n][0],1,V[n][2]])
	E.append([V[n][1],-1,V[n][2]])
D = [int(inputs()) for p in [0]*Q]
E.sort(key = lambda x:x[0])
mini = 1000000001
kouho = [1000000001]
q = 0
d = D[0]
for e in E:
	flag = 0
	if e[0] <= d:
		if  e[1] == 1:
			kouho.append(e[2])
		elif e[1] == -1:
			kouho.remove(e[2])
	if e[0] > d:
		for k in kouho:
			mini = min(k,mini)
		if mini < 1000000001:
			print(mini)
			mini = 1000000001
		else:
			print(-1)
			mini = 1000000001
		flag = 1
		if q < Q-1:
			q = q + 1
			d = D[q]
		else:
			break
	if e[0] <= d and flag == 1:
		if  e[1] == 1:
			kouho.append(e[2])
		elif e[1] == -1:
			kouho.remove(e[2])
for t in [None]*(Q-q):
	print(-1)

Submission status: Runtime Error

Solution code:
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [None]*N
E = []
for n in range(N):
	V[n] = list(map(int,inputs().split()))
	V[n][0] -= V[n][2]
	V[n][1] -= V[n][2]
	E.append([V[n][0],1,V[n][2]])
	E.append([V[n][1],-1,V[n][2]])
D = [int(inputs()) for p in [0]*Q]
E.sort(key = lambda x:x[0])
E.append([1000000001,0,1000000001])
mini = 1000000001
kouho = [1000000001]
q = 0
d = D[0]
for e in E:
	flag = 0
	if e[0] <= d:
		if  e[1] == 1:
			kouho.append(e[2])
		elif e[1] == -1:
			kouho.remove(e[2])
	if e[0] > d:
		for k in kouho:
			mini = min(k,mini)
		if mini < 1000000001:
			print(mini)
			mini = 1000000001
		else:
			print(-1)
			mini = 1000000001
		flag = 1
		if q < Q-1:
			q = q + 1
			d = D[q]
		else:
			break
	if e[0] <= d and flag == 1:
		if  e[1] == 1:
			kouho.append(e[2])
		elif e[1] == -1:
			kouho.remove(e[2])
for t in [None]*(Q-q-1):
	print(-1)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
import sys
N, Q = map(int, input().split())
stx = [tuple(map(int, sys.stdin.readline().split()))[::-1] for _ in range(N)]

stx.sort()

D = [int(sys.stdin.readline()) for _ in range(Q)] 
A = [0]*Q
X = [0]*N
for i, (x, t, s) in enumerate(stx):
    il = bl(D, s-x)
    ir = bl(D, t-x)
    A[il] += 2**i
    A[ir] += 2**i
    X[i] = x
for i in range(1, Q):
    A[i] = A[i]^A[i-1]
for a in A:
    if not a:
        print(-1)
    else:
        print(X[(a & -a).bit_length() - 1])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def INT_(n): return int(n)-1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [input() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    import heapq
    N, Q = MI()
    event = []
    for _ in range(N):
        s, t, x = MI()
        event.append((s - x-0.5, 1, x))
        event.append((t - x-0.5, -1, x))

    for _ in range(Q):
        d = I()
        event.append((d, 0))

    # クエリも含めてソート
    event.sort(key=lambda x: x[0])

    # 工事現場が一番近いところを探すのにO(N)かけると死ぬのでlogNで調べることができるように優先度付きキューも使う
    occur = set()
    occur_priority = []

    for e in event:
        # 工事開始
        if e[1] == 1:
            occur.add(e[2])
            heapq.heappush(occur_priority, e[2])

        # 工事終了
        elif e[1] == -1:
            occur.remove(e[2])

        # クエリ
        elif e[1] == 0:
            if occur:
                while 1:
                    if occur_priority[0] in occur:
                        min_occur = occur_priority[0]
                        break
                    else:
                        heapq.heappop(occur_priority)
                print(min_occur)
            else:
                print(-1)


if __name__ == '__main__':
    main()