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;input=sys.stdin.readline
from bisect import*

n,q=map(int,input().split())
event=[]
stopped={-1}

def doevent(l):
    global stopped
    if l[1]==1:
        if stopped=={-1}:
            stopped=set()
        stopped.add(l[2])
    elif l[1]==-1:
        stopped.remove(l[2])
        if len(stopped)==0:
            stopped={-1}
            
for i in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x,1,x))
    event.append((t-x,-1,x))
event.append((-float("inf"),"x","x"))
event.append((float("inf"),"x","x"))
event.sort(key=lambda x:x[0])
eventtime=[i[0]for i in event]
#print(eventtime)
query=[bisect_right(eventtime,int(input()))-1 for i in range(q)]
#print(query)
c=0
#print(event)
for i in range(2*n):
    doevent(event[i])
    while i==query[c]:
        print(min(stopped))
        c+=1
for i in range(query.count(2*n)):
    print(-1)

Submission status: Runtime Error

Solution code:
import sys;input=sys.stdin.readline
from bisect import*

n,q=map(int,input().split())
event=[]
stopped=set([-1])

def doevent(l):
    global stopped
    if l[1]==1:
        if stopped=={-1}:
            stopped=set()
        stopped.add(l[2])
    elif l[1]==-1:
        stopped.remove(l[2])
        if len(stopped)==0:
            stopped={-1}
            
for i in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x,1,x))
    event.append((t-x,-1,x))
event.append((-float("inf"),"x","x"))
event.append((float("inf"),"x","x"))
event.sort(key=lambda x:x[0])
eventtime=[i[0]for i in event]
#print(eventtime)
query=[bisect_right(eventtime,int(input()))-1 for i in range(q)]+[float("inf")]*100
#print(query)
c=0
#print(event)
for i in range(2*n+1):
    doevent(event[i])
    while i==query[c]:
        print(min(stopped))
        c+=1

Submission status: Runtime Error

Solution code:
import sys;input=sys.stdin.readline
from bisect import*

n,q=map(int,input().split())
event=[]
stopped=set([-1])

def doevent(l):
    global stopped
    if l[1]==1:
        if stopped=={-1}:
            stopped=set()
        stopped.add(l[2])
    elif l[1]==-1:
        stopped.remove(l[2])
        if len(stopped)==0:
            stopped={-1}
            
for i in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x,1,x))
    event.append((t-x,-1,x))
event.append((-float("inf"),"x","x"))
event.append((float("inf"),"x","x"))
event.sort(key=lambda x:x[0])
eventtime=[i[0]for i in event]
#print(eventtime)
query=[bisect_right(eventtime,int(input()))-1 for i in range(q)]+[float("inf")]
#print(query)
c=0
#print(event)
for i in range(2*n+1):
    doevent(event[i])
    while i==query[c]:
        print(min(stopped))
        c+=1

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = deque()
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX.append([x,s-x,t-x])
  Dn = [int(stdin.readline().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  for x,s,t in sorted(list(STX)):
    l = bisect_left(Dn,s)
    r = l
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans


if __name__ == "__main__":
  ans = main()
  n=len(ans)
  for _ in range(n):
    print(heappop(ans)[1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in xrange(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(stdin.readline().rstrip()) for _ in xrange(Q)] + [10**10]
  ans = []

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    r = l
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans


if __name__ == "__main__":
  ans = main()
  while len(ans) > 0:
    print(heappop(ans)[1])

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
kouji=[tuple(map(int,input().split())) for i in range(N)]
kouji=[(S-X,T-X-1,X) for S,T,X in kouji]
kouji.sort(key=lambda x:x[2])
D=[int(input()) for i in range(Q)]
L=1
while L<Q:
    L*=2
inf=float('inf')
D+=[inf]*(L-Q)
K=2*L-1

idx=[0]*K
Range=[(inf,inf)]*K
Min=[inf]*K

idx[0]=(0,L-1)
Range[0]=(D[idx[0][0]],D[idx[0][1]])
for k in range(L-1):
    l,r=idx[k]
    idx[2*k+1]=(l,(l+r)//2)
    idx[2*k+2]=((l+r)//2+1,r)
    Range[2*k+1]=(D[idx[2*k+1][0]],D[idx[2*k+1][1]])
    Range[2*k+2]=(D[idx[2*k+2][0]],D[idx[2*k+2][1]])
def renew(b,e,x,k):
    global Min
    if b==Range[k][0] and e==Range[k][1]:
        Min[k]=min(Min[k],x)
        return
    if Range[2*k+2][0]>e:
        if Min[2*k+1]<x:
            return
        renew(max(b,Range[2*k+1][0]),min(e,Range[2*k+1][1]),x,2*k+1)
    elif Range[2*k+1][1]<b:
        if Min[2*k+2]<x:
            return
        renew(max(b,Range[2*k+2][0]),min(e,Range[2*k+2][1]),x,2*k+2)
    else:
        renew(max(b,Range[2*k+1][0]),Range[2*k+1][1],x,2*k+1)
        renew(Range[2*k+2][0],min(e,Range[2*k+2][1]),x,2*k+2)
    return
for b,e,x in kouji:
    renew(b,e,x,0)
def get(q):
    global Min
    ans=10**10
    now=q
    while True:
        if now==0:
            break
        if ans>Min[now]:
            return Min[now]
        now=(now-1)//2
    if ans>10**9:
        return -1
    return ans
for q in range(Q):
    print(get(q+L-1))

Submission status: Runtime Error

Solution code:
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.size = 2 ** (int.bit_length(N+1))
        self.tree = [0]*(self.size + 1)

    def sum(self, i):
        res = 0
        while i:
            res += self.tree[i]
            i -= (i & -(i))
        return res

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self.tree[i] += x
            i += (i & -(i))


class DammyMap:


    def __init__(self, counter, INF=2**32):
        if type(counter) != Counter:
            counter = Counter(counter)

        self.bit = BIT(len(counter.keys())+3)
        self.key = sorted([-INF, -INF] + sorted(counter.keys()) + [INF])
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(self.val))
        
        for i in range(len(self.key)):
            self.bit.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.bit.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.bit.tree[i] = S[-1] - S[i - (i&-i)]
        
    
    def add(self, val):
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.bit.add(ix, 1)

        
    def update(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.bit.add(ix, v)

    
    def remove(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            
            # 空の値を削除しないかのチェック
            # 時間が厳しそうなときはコメントアウト
            #assert self.bit.sum(ix) - self.bit.sum(ix-1) > 0

            self.bit.add(ix, -v)


    def pop_vals(self, l, r):
        assert l <= r

        vals = []
        rmvs = []

        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.bit.sum(rix)
        lv = self.bit.sum(lix)
        delta = rv - lv
        tv = lv+1
        tix = lix*1
        while delta:
            OK = rix * 1
            NG = tix * 1
            while abs(OK - NG) > 1:
                mid = (OK + NG)//2
                if tv <= self.bit.sum(mid):
                    OK = mid
                else:
                    NG = mid
            c = self.bit.sum(OK)
            d = c - tv + 1
            vals.extend([self.key[OK]*1 for _ in range(d)])
            rmvs.append([OK, d])
            tv += d
            tix = OK
            delta -= d
        
        for ix, d in rmvs:
            self.bit.add(ix, -d)
        return vals


N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)

dmap = DammyMap(D)

for s, t, x in Q:
    val = dmap.get_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x
    dmap.remove(val)

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

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
from collections import deque

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return tuple( int(s) for s in input().split(" ") )

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,q = get_nums_l()

event = []
for i in range(n):
    s,t,x = get_nums_l()
    if t-x > 0:
        event.append((s-x, True, x))
        event.append((t-x, False, x))
event.sort(key=lambda e:e[1])
event.sort(key=lambda e:e[0])
d = list(get_nums_n(q))

last = -1
s = set()
i_max = len(event) * 2
for di in d:
    while(((last+1) < i_max) and (event[last + 1][0] <= di) ):
        now = last+1
        e = event[now]
        if(e[1]):
            s.add(e[2])
        else:
            s.remove(e[2])
        last = now
    
    if(s):
        print(min(s))
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
from collections import deque

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return tuple( int(s) for s in input().split(" ") )

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,q = get_nums_l()

event = []
for i in range(n):
    s,t,x = get_nums_l()
    if t-x > 0:
        event.append((s-x, True, x))
        event.append((t-x, False, x))
event.sort(key=lambda e:e[1])
event.sort(key=lambda e:e[0])
d = list(get_nums_n(q))

last = -1
s = set()
for di in d:
    while(((last+1) < n*2) and (event[last + 1][0] <= di) ):
        now = last+1
        e = event[now]
        if(e[1]):
            s.add(e[2])
        else:
            s.remove(e[2])
        last = now
    
    if(s):
        print(min(s))
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
from collections import deque

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return tuple( int(s) for s in input().split(" ") )

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,q = get_nums_l()

event = []
for i in range(n):
    s,t,x = get_nums_l()
    if t-x > 0:
        event.append((max(0,s-x), True, x))
        event.append((max(0,t-x), False, x))
event.sort(key=lambda e:e[1])
event.sort(key=lambda e:e[0])
d = list(get_nums_n(q))

last = -1
s = set()
for di in d:
    while(((last+1) < n*2) and (event[last + 1][0] <= di) ):
        now = last+1
        e = event[now]
        if(e[1]):
            s.add(e[2])
        else:
            s.remove(e[2])
        last = now
    
    if(s):
        print(min(s))
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from heapq import heappush,heappop
from collections import deque
from sys import stdin,stdout


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [10**10] * Q
  ans = {}
  for i in range(Q):
    Dn[i] = int(stdin.readline().rstrip())
    ans[Dn[i]] = -1

  for x,s,t in sorted(list(STX)):
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      ans[Dn[l]] = x
      Dn.pop(l)

  return ans


if __name__ == "__main__":
  ans = main()
  for d in sorted(list(ans.keys())):
    print(ans[d])

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
from collections import deque

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return tuple( int(s) for s in input().split(" ") )

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,q = get_nums_l()

event = []
for i in range(n):
    s,t,x = get_nums_l()
    event.append((max(0,s-x), True, x))
    event.append((max(0,t-x), False, x))
event.sort(key=lambda e:e[1])
event.sort(key=lambda e:e[0])
d = list(get_nums_n(q))

last = -1
s = set()
for di in d:
    while(((last+1) < n*2) and (event[last + 1][0] <= di) ):
        now = last+1
        e = event[now]
        if(e[1]):
            s.add(e[2])
        else:
            s.remove(e[2])
        last = now
    
    if(s):
        print(min(s))
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
from collections import deque

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return tuple( int(s) for s in input().split(" ") )

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,q = get_nums_l()

event = []
for i in range(n):
    s,t,x = get_nums_l()
    event.append((max(0,s-x), True, x))
    event.append((max(0,t-x), False, x))
event.sort(key=lambda e:e[1])
event.sort(key=lambda e:e[0])
print(event)
d = list(get_nums_n(q))

last = -1
s = set()
for di in d:
    while(((last+1) < n*2) and (event[last + 1][0] <= di) ):
        now = last+1
        e = event[now]
        if(e[1]):
            s.add(e[2])
        else:
            s.remove(e[2])
        last = now
    
    if(s):
        print(min(s))
    else:
        print(-1)

Submission status: Runtime Error

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

# i番目の人の座標を計算
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])

Submission status: Runtime Error

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

# i番目の人の座標を計算
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])

Submission status: Runtime Error

Solution code:
import bisect
import heapq
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, Q = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

# (d, x, x のインデックス) のリスト
lows = []
highs = []

for xi, [s, t, x] in enumerate(STX):
    # [lo, hi) に出発した人は x で止まる
    lo = bisect.bisect_left(D, s - x)
    hi = bisect.bisect_left(D, t - x)
    lows.append((D[lo], x, xi))
    highs.append((D[hi], x, xi))

lows.sort()
highs.sort()
L = 0
r = 0
# (x, D のインデックス)
heap = []
used = [False for _ in range(len(lows))]

for i, d in enumerate(D):
    while L < len(lows) and lows[L][0] <= d:
        heapq.heappush(heap, (lows[L][1], lows[L][2]))
        L += 1
    while r < len(highs) and highs[r][0] <= d:
        used[highs[r][2]] = True
        r += 1
    while heap and used[heap[0][1]]:
        heapq.heappop(heap)
    if heap:
        print(heap[0][0])
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
import bisect
import heapq
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, Q = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

# (d, x, x のインデックス) のリスト
lows = []
highs = []

for xi, [s, t, x] in enumerate(STX):
    # [lo, hi) に出発した人は x で止まる
    lo = bisect.bisect_left(D, s - x)
    hi = bisect.bisect_left(D, t - x)
    lows.append((D[lo], x, xi))
    highs.append((D[hi], x, xi))

lows.sort()
highs.sort()
L = 0
r = 0
# (x, D のインデックス)
heap = []
used = set()

for i, d in enumerate(D):
    while L < len(lows) and lows[L][0] <= d:
        heapq.heappush(heap, (lows[L][1], lows[L][2]))
        L += 1
    while r < len(highs) and highs[r][0] <= d:
        used.add(highs[r][2])
        r += 1
    while heap and heap[0][1] in used:
        heapq.heappop(heap)
    if heap:
        print(heap[0][0])
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
import bisect
import heapq
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N, Q = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = np.array([int(input()) for _ in range(Q)])

# (d, x, x のインデックス) のリスト
lows = []
highs = []

for xi, [s, t, x] in enumerate(STX):
    # [lo, hi) に出発した人は x で止まる
    lo = bisect.bisect_left(D, s - x)
    hi = bisect.bisect_left(D, t - x)
    lows.append((D[lo], x, xi))
    highs.append((D[hi], x, xi))

lows.sort()
highs.sort()
L = 0
r = 0
# (x, D のインデックス)
heap = []
used = set()

for i, d in enumerate(D):
    while L < len(lows) and lows[L][0] <= d:
        heapq.heappush(heap, (lows[L][1], lows[L][2]))
        L += 1
    while r < len(highs) and highs[r][0] <= d:
        used.add(highs[r][2])
        r += 1
    while heap and heap[0][1] in used:
        heapq.heappop(heap)
    if heap:
        print(heap[0][0])
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
def main():
    import sys,heapq
    from collections import defaultdict
    input = sys.stdin.readline

    n,q = map(int,input().split())
    #used[i]:0より大きいならi
    used = defaultdict(int)
    tank = []

    p = []
    for i in range(n):
        s,t,x = map(int,input().split())
        p.append((s-x,x))
        p.append((t-x-0.5,x))
    p.sort()

    cnt = 0
    for i in range(q):
        d = int(input())
        while cnt<=len(p)-1 and p[cnt][0] <= d:
            w = p[cnt][1]
            if int(p[cnt][0]) == p[cnt][0]:
                used[w] += 1
                heapq.heappush(tank,w)
            else:
                used[w] -= 1
            cnt += 1
        while True:
            if len(tank) == 0:
                print(-1)
                break
            kouho = tank[0]
            if used[kouho] > 0:
                print(kouho)
                break
            else:
                heapq.heappop(kouho)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N,Q =map(int,input().split())
event = []
sto = [[int(i)for i in input().split()]for _ in range(N)]
for (s,t,x) in sto:
    event.append([s-x,1,x])
    event.append([t-x,-1,x])
D =[int(input())for _ in range(Q)]
stoset =set()

n = 0
sta =False
event = sorted(event,key =lambda x:x[0])
for (t,s,x) in event:
    while D[n] < t:
        if len(list(stoset))!=0:
            print(min(list(stoset)))
        else:
            print(-1)
        n += 1
        if n==Q:
            sta = True
            break
    if sta:
        break
    if s==1:
        stoset.add(x)
    else:
        stoset.remove(x)
while n<Q:
    if len(list(stoset))!=0:
        print(min(list(stoset)))
    else:
        print(-1)
    n += 1

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N,Q =map(int,input().split())
event = []
sto = [[int(i)for i in input().split()]for _ in range(N)]
for (s,t,x) in sto:
    event.append([s-x,1,x])
    event.append([t-x,-1,x])
D =[int(input())for _ in range(Q)]
stoset =set()

n = 0
event = sorted(event,key =lambda x:x[0])
for (t,s,x) in event:
    while D[n] < t:
        if len(list(stoset))!=0:
            print(min(list(stoset)))
        else:
            print(-1)
        n += 1
        if n==Q:
            break
    if s==1:
        stoset.add(x)
    else:
        stoset.remove(x)
while n<Q:
    if len(list(stoset))!=0:
        print(min(list(stoset)))
    else:
        print(-1)
    n += 1

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N,Q =map(int,input().split())
event = []
sto = [[int(i)for i in input().split()]for _ in range(N)]
for (s,t,x) in sto:
    event.append([s-x,1,x])
    event.append([t-x,-1,x])
D =[int(input())for _ in range(Q)]
stoset =set()

n = 0
event = sorted(event,key =lambda x:x[0])
for (t,s,x) in event:
    while D[n] < t:
        if len(list(stoset))!=0:
            print(min(list(stoset)))
        else:
            print(-1)
        n += 1
    if s==1:
        stoset.add(x)
    else:
        stoset.remove(x)
while n<Q:
    if len(list(stoset))!=0:
        print(min(list(stoset)))
    else:
        print(-1)
    n += 1

Submission status: Runtime Error

Solution code:
from bisect import bisect, bisect_left
from collections import Counter
from functools import reduce
from itertools import accumulate
from operator import itemgetter, xor

import sys
input = sys.stdin.readline

def inpl(): return list(map(int, input().split()))

class BIT:
    def __init__(self, N):
        # Nは入れたい要素の個数
        self.size = 2 ** (int.bit_length(N+1))
        self.tree = [0]*(self.size + 1)

    def sum(self, i):
        res = 0
        while i:
            res += self.tree[i]
            i -= (i & -(i))
        return res

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self.tree[i] += x
            i += (i & -(i))


class RABIT():
    # range add BIT
    def __init__(self, N):
        self.bit0 = BIT(N)
        self.bit1 = BIT(N)

    def sum(self, i):
        return i*self.bit1.sum(i) + self.bit0.sum(i)

    def add_range(self, l, r, x):
        self.bit0.add(l, -x*(l-1))
        self.bit1.add(l, x)
        self.bit0.add(r+1, x*r)
        self.bit1.add(r+1, -x)

    def get_range(self, l, r):
        return self.sum(r) - self.sum(l-1)

class DammyMap:
    """
    座圧してc++のmapみたいな操作が必要な問題に対応する
    要素の追加、削除がO(logN)
    指定した区間の取り出しがO(logNlogN)
    """
    def __init__(self, counter, INF=2**31):
        if type(counter) != Counter:
            counter = Counter(counter)

        self.rabit = RABIT(len(counter.keys()) + 2)
        self.key = sorted([-INF] + sorted(counter.keys()) + [INF])
        self.ukey = set(counter.keys())
        self.val = [counter[k] for k in self.key]
        S = list(accumulate(accumulate(self.val)))

        for i in range(len(self.key)):
            self.rabit.bit0.tree[i] = S[i] - S[i - (i&-i)]
        for i in range(len(self.key), len(self.rabit.bit0.tree)):
            j = i - (i&-i)
            if j < len(S):
                self.rabit.bit0.tree[i] = S[-1] - S[i - (i&-i)]
    
    def add(self, val):
        if not val in self.ukey:
            raise KeyError
        ix = bisect_left(self.key, val)
        assert self.key[ix] == val
        self.rabit.add_range(ix, len(self.rabit.bit0.tree)-1, 1)
    
    def update(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.rabit.add_range(ix,  len(self.rabit.bit0.tree)-1, v)

    def remove(self, vals):
        for k, v in Counter(vals).items():
            ix = bisect_left(self.key, k)
            if self.key[ix] != k:
                raise KeyError
            self.rabit.add_range(ix, len(self.rabit.bit0.tree)-1, -v)
    
    def get_vals(self, l, r):
        """
        [l, r]に含まれるアイテムを返す
        """
        assert l <= r

        vals = []
        rix = bisect(self.key, r) - 1
        lix = bisect_left(self.key, l) - 1
        # (lix, rix]になるのに注意
        rv = self.rabit.get_range(rix, rix)
        lv = self.rabit.get_range(lix, lix) if lix else 0
        delta = rv - lv
        tv = lv+1
        tix = lix*1
        while delta:
            OK = rix * 1
            NG = tix * 1
            while abs(OK - NG) > 1:
                mid = (OK + NG)//2
                if tv <= self.rabit.get_range(mid, mid):
                    OK = mid
                else:
                    NG = mid
            c = self.rabit.get_range(OK, OK)
            d = c - tv + 1
            vals.extend([self.key[OK]*1 for _ in range(d)])
            tv += d
            tix = OK
            delta -= d
        return vals

N, M = inpl()
Q = sorted([inpl() for _ in range(N)], key=itemgetter(2))
D = [int(input()) for _ in range(M)]
rD = {v:i for i, v in enumerate(D)}
ans = [-1]*(M)

dmap = DammyMap(D)

for s, t, x in Q:
    val = dmap.get_vals(s-x, t-1-x)
    for v in val:
        ans[rD[v]] = x
    dmap.remove(val)

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

Submission status: Runtime Error

Solution code:
N,Q=list(map(int,input().split()))
Event=[]
for i in range(N):
    S,T,X=(list(map(int,input().split())))
    Event.append((S-X,1,X))
    Event.append((T-X,-1,X))
Event=sorted(Event,key=lambda x:x[0])
s=set()
iev=0
for i in range(Q):
    dd=int(input())
    while iev<2*N and Event[iev][0]<=dd:
        if Event[iev][1]==1:
            s.add(Event[iev][2])
        else:
            s.remove(Event[iev][2])
        iev+=1
    print(min(s) if s else -1)

Submission status: Runtime Error

Solution code:
N,Q=list(map(int,input().split()))
Event=[]
STX=[]
for i in range(N):
    S,T,X=(list(map(int,input().split())))
    STX.append((S,T,X))
    Event.append((S-X,1,X))
    Event.append((T-X,-1,X))
Event=sorted(Event,key=lambda x:x[0])
D=[]
s=set()
iev=0
for i in range(Q):
    dd=int(input())
    while iev<2*N and Event[iev][0]<=dd:
        if Event[iev][1]==1:
            s.add(Event[iev][2])
        else:
            s.remove(Event[iev][2])
        iev+=1
    print(min(s) if s else -1)

Submission status: Runtime Error

Solution code:
N,Q=list(map(int,input().split()))
Event=[]
STX=[]
for i in range(N):
    S,T,X=(list(map(int,input().split())))
    STX.append((S,T,X))
    S0.append((max(S-0.5-X,0),X))
    T0.append((max(T-0.5-X,0),X))
    Event.append((S-X,1,X))
    Event.append((T-X,-1,X))
Event=sorted(Event,key=lambda x:x[0])
D=[]
s=set()
iev=0
for i in range(Q):
    dd=int(input())
    while iev<2*N and Event[iev][0]<=dd:
        if Event[iev][1]==1:
            s.add(Event[iev][2])
        else:
            s.remove(Event[iev][2])
        iev+=1
    print(min(s) if s else -1)

Submission status: Runtime Error

Solution code:
#test
def hersCode(L, n):
  ok = len(L)
  ng = l
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok

def main():
  N, Q = list(map(int, input().split()))
  STX = [list(map(int, input().split())) for _ in range(N)]
  D = [int(input()) for _ in range(Q)]

  STX.sort(key = lambda x: x[2])

  L = [[-1, -1]] * Q
  for s, t, x in STX:
    l = hersCode(D, s - x)
    r = hersCode(D, t - x)
    continue
    while l < r:
      if L[l][1] == -1:
        L[l] = [x, r]
        l += 1
      else:
        l = L[l][1]

  for i in L:
    print(i[0])

main()

Submission status: Runtime Error

Solution code:
#test
def hersCode(L, n):
  ok = len(L)
  ng = l
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok

def main():
  N, Q = list(map(int, input().split()))
  STX = [list(map(int, input().split())) for _ in range(N)]
  D = [int(input()) for _ in range(Q)]

  STX.sort(key = lambda x: x[2])

  L = [[-1, -1]] * Q
  for s, t, x in STX:
    l = hersCode(D, s - x)
    r = hersCode(D, t - x)
    continue()
    while l < r:
      if L[l][1] == -1:
        L[l] = [x, r]
        l += 1
      else:
        l = L[l][1]

  for i in L:
    print(i[0])

main()