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: Accepted

Solution code:
from collections import defaultdict as di
import heapq

def main():
    inp = readnumbers()
    ii = 0
    
    n = inp[ii]
    ii += 1
    q = inp[ii]
    ii += 1

    starts = []
    ends = []

    for _ in range(n):
        s = inp[ii]
        ii += 1
        t = inp[ii]
        ii += 1
        x = inp[ii]
        ii += 1

        starts.append((s-x,x))
        ends.append((t-x,x))

    starts.sort(reverse=True)
    ends.sort(reverse=True)

    D = inp[ii:ii+q]
    ii += q

    count = di(int)
    active = []

    for d in D:
        while starts and starts[-1][0]<=d:
            _,x = starts.pop()
            heapq.heappush(active,x)
        while ends and ends[-1][0]<=d:
            _,x = ends.pop()
            count[x] += 1

        while active and count[active[0]]>0:
            x = heapq.heappop(active)
            count[x] -= 1

        if active:
            print active[0]

        else:
            print -1
        
        
    

######## Python 2 and 3 footer by Pajenegod and c1729

# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using binary strings in PyPy3
# but its syntax is different which makes it kind of a mess to use.

# So on cf, use PyPy2 for best string performance.

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'

# Read all remaining integers in stdin, type is given by optional argument, this is fast
def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'0' [0]:
        A.append(sign*numb)
    return A

if __name__== "__main__":
  main()

Submission status: Runtime Error

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18 if not DBG else 99999
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)


# # # # class Segtree # # # #

#      0
#   1     2
# 3   4  5  6
#       :
# leaf i - n-1+i
# parent   - (i-1)//2
# children - 2*i+1, 2*i+2

class Segtree:
    # modify UNIT and oper depending on the reduce operation

    #UNIT = 0  # sum/or:0 and:fff..f min:BIG max:-BIG gcd:0 lcm:1 ..

    #@classmethod
    #def oper(c,x,y):
    #    return x|y  # sum:+ or/and/min/max/gcd/lcm:(same)

    # call like this: sgt = Segtree(n, 0, lambda x,y: max(x,y))

    def __init__(s,l,unit,oper):
        s.unit = unit
        s.oper = oper
        s.n = 1
        while s.n<l:
            s.n *= 2
        s.ary = [s.unit for i in range(2*s.n-1)]

    def get(s,i):
        return s.ary[i+s.n-1]

    def set(s,i,v):
        k = i+s.n-1
        s.ary[k] = v
        while k>0:
            k = (k-1)//2
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def setary(s,a):
        for i,v in enumerate(a):
            s.ary[i+s.n-1] = v
        for k in range(s.n-2,-1,-1):
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def query(s,x,y):
        l = x+s.n-1
        r = y+s.n-1
        res = s.unit
        while l<r:
            if not l%2:
                res = s.oper(res,s.ary[l])
                l += 1
            if not r%2:
                r -= 1
                res = s.oper(res,s.ary[r])
            l >>= 1
            r >>= 1
        return res


# # # # class Segtree end # # # #

n,q = inm()
xs = set([])
stx = []
for i in range(n):
    s,t,x = inm()
    xs.add(x)
    xs.add(s-x)
    xs.add(t-x)
    stx.append((s-x,t-x,x))
stx.sort()

di = []
ans = [-1]*q
for i in range(q):
    d = inn()
    xs.add(d)
    di.append(d)

x2i = {}
i2x = list(xs)
m = len(xs)
i2x.sort()
for i,x in enumerate(i2x):
    x2i[x] = i

stx2 = []
for i in range(n):
    s,t,x = stx[i]
    stx2.append((x2i[s],x2i[t],x2i[x]))
d2 = [x2i[d] for d in di]

#ddprint(x2i)
#ddprint(i2x)
#ddprint(stx2)
#ddprint(d2)

import heapq

sgt = Segtree(m,BIG,lambda x,y: min(x,y))
top = 0
t2x = {}
for j in range(q):
    if False and DBG and j%100==0:
        #for i in range(m):
        #    printn(f"{sgt.get(i)} ")
        print('. ')
    d = d2[j]
    #ddprint(f"{d=}")
    while top<n:
        s,t,x = stx2[top]
        if s>d:
            break
        sgt.set(x,t)
        if t not in t2x:
            t2x[t] = []
        heapq.heappush(t2x[t],x)
        top += 1
    #ddprint(11)
    while True:
        t = sgt.query(0,m)
        if t>d:
            break
        else:
            while len(t2x[t])>0:
                z = heapq.heappop(t2x[t])
                sgt.set(z,BIG)
    #ddprint(22)
    if t==BIG:
        print(-1)
    else:
        z = heapq.heappop(t2x[t])
        print(i2x[z])
        heapq.heappush(t2x[t],z)

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, Q = LI()
    sections = []
    D = []

    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        sections.append((s, t, x))

    for _ in range(Q):
        D.append(I())
    sections = sorted(sections, key=lambda x: x[-1])

    section_end_ix = collections.defaultdict(list)

    filled = [-1] * Q
    for sec in sections:
        l = bisect.bisect_left(D, sec[0])
        r = bisect.bisect_left(D, sec[1])
        x = sec[2]
        # 調整 [0, 2, 5, 8, 9]、区間[1, 5]のとき、l = 1, r = 3になる。r = 2にする。
        # 調整 [0, 2, 5, 8, 9]、区間[2, 4]のとき、l = 1, r = 2になる。r = 1にする。
        r -= 1
        if r < 0:
            continue
        section_end_ix[x].append(r)
        ix = l
        while ix <= r:
            val_X = filled[ix] # 進める距離
            # 既に埋まってたら終点までスキップ
            if val_X > -1:
                _i = bisect.bisect_right(section_end_ix[val_X], ix) # section_end_ix[val_X]: 進める距離の終点のindexがのった配列
                # ix = 4、section_end_ix[val_X] = [2, 4, 7]のとき、2がかえる。

                # 終点までスキップ
                ix = section_end_ix[val_X][_i]
            # うまってなかったら埋める
            else:
                filled[ix] = x
            ix += 1

    for x in filled:
        print(x)
main()

Submission status: Runtime Error

Solution code:
import heapq
n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s-x, 1, x))
    event.append((t-x, -1, x))

event.sort()
heap = []
xs = set([])

d = [int(input()) for _ in range(q)]
ans = [-1] * q
index = 0
for t, query, x in event:
    if d[index] < t:
        if not xs:
            pass
        else:
            while heap:
                tmp = heapq.heappop(heap)
                if tmp in xs:
                    heapq.heappush(heap, tmp)
                    ans[index] = tmp
                    break
        index += 1
        if index == q:
            break

    if query == 1:
        xs.add(x)
        heapq.heappush(heap, x)
    else:
        xs.remove(x)

    cnt[t] -= 1

while index < q:
    while heap:
        tmp = heapq.heappop(heap)
        if tmp in xs:
            heapq.heappush(heap, tmp)
            ans[index] = tmp
            break
    index += 1

print("\n".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
import heapq
n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s-x, 1, x))
    event.append((t-x, -1, x))

event.sort(key=lambda y: y[0])
heap = []
xs = set([])

d = [int(input()) for _ in range(q)]
ans = [-1] * q
index = 0
for t, query, x in event:
    if d[index] < t:
        if not xs:
            pass
        else:
            while heap:
                tmp = heapq.heappop(heap)
                if tmp in xs:
                    heapq.heappush(heap, tmp)
                    ans[index] = tmp
                    break
        index += 1
        if index == q:
            break

    if query == 1:
        xs.add(x)
        heapq.heappush(heap, x)
    else:
        xs.remove(x)

while index < q:
    while heap:
        tmp = heapq.heappop(heap)
        if tmp in xs:
            heapq.heappush(heap, tmp)
            ans[index] = tmp
            break
    index += 1

print("\n".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
import heapq
n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s-x, 1, x))
    event.append((t-x, -1, x))

event.sort(key=lambda y: y[0])
heap = []
xs = set([])

d = [int(input()) for _ in range(q)]
ans = [-1] * q
index = 0
for t, query, x in event:
    if d[index] < t:
        if not xs:
            pass
        else:
            while heap:
                tmp = heapq.heappop(heap)
                if tmp in xs:
                    heapq.heappush(heap, tmp)
                    ans[index] = tmp
                    break
        index += 1
        if index == q:
            break

    if query == 1:
        xs.add(x)
        heapq.heappush(heap, x)
    else:

        xs.remove(x)


print("\n".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
import heapq
n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s-x, 1, x))
    event.append((t-x, -1, x))

event.sort(key=lambda y: y[0])
heap = []
xs = set([])

d = [int(input()) for _ in range(q)]
ans = [-1] * q
index = 0
for t, query, x in event:
    if d[index] < t:
        if not xs:
            pass
        else:
            while heap:
                tmp = heapq.heappop(heap)
                if tmp in xs:
                    heapq.heappush(tmp)
                    ans[index] = tmp
                    break
            print("----------")
        index += 1
        if index == q:
            break

    if query == 1:
        xs.add(x)
        heapq.heappush(heap, x)
    else:
        
        xs.remove(x)
    

print("\n".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
from bisect import bisect_left
n,q=map(int,input().split())
stop=[]
for i in range(n):
	s,t,x=map(int,input().split())
	stop.append((s,t,x))
stop.sort(key=lambda x:x[2])
d=[int(input())for i in range(q)]

ans=[-1]*q
for s,t,x in stop:
	l=bisect_left(d,s-x)
	r=bisect_left(d,t-x)
    for i in range(l, r):
		if ans == -1:
			ans[i] = x
            
for x in ans:
	print(x)

Submission status: Runtime Error

Solution code:
import bisect

INF = 10**9 + 1

N, Q = [int(x) for x in input().split()]

data = []
for i in range(N):
    S, T, X = [int(x) for x in input().split()]
    data.append([X, S, T])
data = sorted(data, reverse=True)

D = []
for i in range(Q):
    D.append(int(input()))

dist = [INF]*Q
for i in range(N):
    print(dist)
    [X, S, T] = data[i]
    l = bisect.bisect_left(D, S - X - 0.5)
    r = bisect.bisect_right(D, T - X - 0.5)
    dist = dist[:l] + [X]*(r - l) + dist[r:]

for i in range(Q):
    if dist[i] == INF:
        print(-1)
    else:
        print(dist[i])

Submission status: Runtime Error

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

N, Q = map(int, input().split())
A = []
for i in range(N):
	S, T, X = map(int, input().split())
	A.append((X, S, T))
A.sort()
D = []
for i in range(Q):
	d = int(input())
	D.append([d, i])
for i, d in enumerate(D):
	
D.sort()
ans = [-1] * Q

donecnt = 0
donei = set()
for i in range(N):
	X, S, T = A[i]
	l = bisect(D, [S - X, -1])
	r = bisect(D, [T - X, -1])
	for j in range(l, r):
		if j in donei:
			continue
		ans[D[j][1]] = X
		donei.add(j)
		donecnt += 1
		if donecnt == Q:
			break
	if donecnt == Q:
		break

for i in range(Q):
	print(ans[i])

Submission status: Runtime Error

Solution code:
import numpy as np
import collections
import bisect
import sys
sys.setrecursionlimit(10**9)


from numba import njit

@njit(cache=True)
def zarts(X,x): # 座標圧縮
    return np.searchsorted(X,x)

    
INF=10**18
def prepare(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]",L,R):
    # heapq.heapify()
    count = 0
    for i in range(N):
        l = S[i] - X[i]
        r = T[i] - X[i]

        pos_l = zarts(D,l)
        pos_r = zarts(D,r)

        if pos_l == pos_r: continue
        # bisect.insort_left(L[pos_l],X[i])
        # bisect.insort_left(R[pos_r],X[i])

        L[pos_l][count] = X[i]
        R[pos_r][count] = X[i]
        count += 1

    # print(L[:count])

    return L,R


def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]",L,R):
    worked = set()
    for q in range(Q):
        # print(worked)
        d = q
        ls = L[d]
        rs = R[d]

        for i in range(len(rs)):
            x = int(rs[i])
            if x == INF: break
            
            if x in worked:
                worked.remove(x)
        
        for i in range(len(ls)):
            x = int(ls[i])
            if x == INF: break
            
            worked.add(x)

        if len(worked) == 0:
            print(-1)
            continue

        x = min(worked)
        print(x)



    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    T = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    X = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    # X = [(int(),int())] * (N)  # type: "List[int]"
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
        # X[i] = (-1 * int(next(tokens)),i)
    D = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    D = np.array(D)

    L = np.full((Q+10,N+10),INF,dtype=np.int64)
    R = np.full((Q+10,N+10),INF,dtype=np.int64)
    L,R = prepare(N, Q, S, T, X, D, L,R)
    L = np.sort(L,1)
    R = np.sort(R,1)

    solve(N, Q, S, T, X, D,L,R)


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('zarts', '(i8[:],i8,)')(zarts)
    cc.export('prepare', '(i8,i8,i8[:],i8[:],i8[:],i8[:],i8[:,:],i8[:,:],)')(prepare)
    cc.export('solve', '(i8,i8,i8[:],i8[:],i8[:],i8[:],i8[:,:],i8[:,:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    # cc_export()
    try:
        from my_module import zarts
        from my_module import prepare
        from my_module import solve

    except:
        cc_export()
        exit()

    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import collections
import bisect
import sys
sys.setrecursionlimit(10**9)


from numba import njit

@njit(cache=True)
def zarts(X,x): # 座標圧縮
    return np.searchsorted(X,x)

    
INF=10**18
def prepare(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):

    L = np.full((Q+10,N+10),INF,dtype=np.int64)
    R = np.full((Q+10,N+10),INF,dtype=np.int64)
    # heapq.heapify()
    count = 0
    for i in range(N):
        l = S[i] - X[i]
        r = T[i] - X[i]

        pos_l = zarts(D,l)
        pos_r = zarts(D,r)

        if pos_l == pos_r: continue
        # bisect.insort_left(L[pos_l],X[i])
        # bisect.insort_left(R[pos_r],X[i])

        L[pos_l][count] = X[i]
        R[pos_r][count] = X[i]
        count += 1

    # print(L[:count])

    return L,R


def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]",L,R):
    worked = set()
    for q in range(Q):
        # print(worked)
        d = q
        ls = L[d]
        rs = R[d]

        for i in range(len(rs)):
            if rs[i] == INF: break
            x = int(rs[i])

            if x in worked:
                worked.remove(x)
        
        for i in range(len(ls)):
            if ls[i] == INF: break
            x = int(ls[i])
            worked.add(x)

        if not worked:
            print(-1)
            continue

        x = min(worked)
        print(x)



    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    T = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    X = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    # X = [(int(),int())] * (N)  # type: "List[int]"
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
        # X[i] = (-1 * int(next(tokens)),i)
    D = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    D = np.array(D)


    L,R = prepare(N, Q, S, T, X, D)
    L = np.sort(L,1)
    R = np.sort(R,1)

    solve(N, Q, S, T, X, D,L,R)


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('zarts', '(i8[:],i8,)')(zarts)
    cc.export('prepare', '(i8,i8,i8[:],i8[:],i8[:],i8[:],)')(prepare)
    cc.export('solve', '(i8,i8,i8[:],i8[:],i8[:],i8[:],i8[:,:],i8[:,:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    # cc_export()
    try:
        from my_module import zarts
        from my_module import prepare
        from my_module import solve

    except:
        cc_export()
        exit()

    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import collections
import bisect
import sys
sys.setrecursionlimit(10**9)


from numba import njit

@njit(cache=True)
def zarts(X,x): # 座標圧縮
    return np.searchsorted(X,x)

    
INF=10**18
def prepare(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):

    L = np.full((Q+10,N+10),INF,dtype=np.int64)
    R = np.full((Q+10,N+10),INF,dtype=np.int64)
    # heapq.heapify()
    count = 0
    for i in range(N):
        l = S[i] - X[i]
        r = T[i] - X[i]

        pos_l = zarts(D,l)
        pos_r = zarts(D,r)

        if pos_l == pos_r: continue
        # bisect.insort_left(L[pos_l],X[i])
        # bisect.insort_left(R[pos_r],X[i])

        L[pos_l][count] = X[i]
        R[pos_r][count] = X[i]
        count += 1

    # print(L[:count])

    return L,R


def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]",L,R):
    worked = set()
    for q in range(Q):
        # print(worked)
        d = q
        ls = L[d]
        rs = R[d]

        for i in range(len(rs)):
            if rs[i] == INF: break
            worked.remove(rs[i])
        
        for i in range(len(ls)):
            if ls[i] == INF: break
            worked.add(ls[i])

        if not worked:
            print(-1)
            continue

        x = min(worked)
        print(x)



    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    T = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    X = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    # X = [(int(),int())] * (N)  # type: "List[int]"
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
        # X[i] = (-1 * int(next(tokens)),i)
    D = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    D = np.array(D)


    L,R = prepare(N, Q, S, T, X, D)
    L = np.sort(L,1)
    R = np.sort(R,1)

    solve(N, Q, S, T, X, D,L,R)


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('zarts', '(i8[:],i8,)')(zarts)
    cc.export('prepare', '(i8,i8,i8[:],i8[:],i8[:],i8[:],)')(prepare)
    cc.export('solve', '(i8,i8,i8[:],i8[:],i8[:],i8[:],i8[:,:],i8[:,:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    # cc_export()
    try:
        from my_module import zarts
        from my_module import prepare
        from my_module import solve

    except:
        cc_export()
        exit()

    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import collections
import bisect
import sys
sys.setrecursionlimit(10**9)


from numba import njit

@njit(cache=True)
def zarts(X,x): # 座標圧縮
    return np.searchsorted(X,x)

    
INF=10**18
def prepare(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):

    L = np.full((Q,N),INF,dtype=np.int64)
    R = np.full((Q,N),INF,dtype=np.int64)
    # heapq.heapify()
    count = 0
    for i in range(N):
        l = S[i] - X[i]
        r = T[i] - X[i]

        pos_l = zarts(D,l)
        pos_r = zarts(D,r)

        if pos_l == pos_r: continue
        # bisect.insort_left(L[pos_l],X[i])
        # bisect.insort_left(R[pos_r],X[i])

        L[pos_l][count] = X[i]
        R[pos_r][count] = X[i]
        count += 1

    # print(L[:count])

    return L,R


def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]",L,R):
    worked = set()
    for q in range(Q):
        # print(worked)
        d = q
        ls = L[d]
        rs = R[d]

        for i in range(len(rs)):
            if rs[i] == INF: break
            worked.remove(rs[i])
        
        for i in range(len(ls)):
            if ls[i] == INF: break
            worked.add(ls[i])

        if not worked:
            print(-1)
            continue

        x = min(worked)
        print(x)



    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    T = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    X = np.zeros(N,dtype=np.int64)  # type: "List[int]"
    # X = [(int(),int())] * (N)  # type: "List[int]"
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
        # X[i] = (-1 * int(next(tokens)),i)
    D = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    D = np.array(D)


    L,R = prepare(N, Q, S, T, X, D)
    L = np.sort(L,1)
    R = np.sort(R,1)

    solve(N, Q, S, T, X, D,L,R)


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('zarts', '(i8[:],i8,)')(zarts)
    cc.export('prepare', '(i8,i8,i8[:],i8[:],i8[:],i8[:],)')(prepare)
    cc.export('solve', '(i8,i8,i8[:],i8[:],i8[:],i8[:],i8[:,:],i8[:,:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    try:
        from my_module import zarts
        from my_module import prepare
        from my_module import solve

    except:
        cc_export()
        exit()

    main()

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python3
import collections
import bisect
import sys
sys.setrecursionlimit(10**9)

def zarts(X,x): # 座標圧縮
    return bisect.bisect_left(X,x)

    
INF=10**20
def solve(N: int, Q: int, S: "List[int]", T: "List[int]", X: "List[int]", D: "List[int]"):

    pos = D.copy()
    L = collections.defaultdict(lambda: [])
    R = collections.defaultdict(lambda: [])

    # heapq.heapify()
    for i in range(N):
        l = S[i] - X[i]
        r = T[i] - X[i]

        pos_l = zarts(D,l)
        pos_r = zarts(D,r)

        bisect.insort_left(L[pos_l],X[i])
        bisect.insort_left(R[pos_r],X[i])
    

    worked = set()
    for q in range(Q):
        # print(worked)
        d = q
        ls = L[d]
        rs = R[d]

        while rs:
            worked.remove(rs.pop())
        
        while ls:
            worked.add(ls.pop())

        if not worked:
            print(-1)
            continue

        x = min(worked)
        print(x)



    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = [int()] * (N)  # type: "List[int]"
    T = [int()] * (N)  # type: "List[int]"
    X = [int()] * (N)  # type: "List[int]"
    # X = [(int(),int())] * (N)  # type: "List[int]"
    for i in range(N):
        S[i] = int(next(tokens))
        T[i] = int(next(tokens))
        X[i] = int(next(tokens))
        # X[i] = (-1 * int(next(tokens)),i)
    D = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    solve(N, Q, S, T, X, D)



if __name__ == "__main__":
    main()