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:
from collections import deque
import sys
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e.sort()
q = deque()
for _ in range(p):
    q.append(int(input()))
s=set()
#print(e)
for t,f,x in e:
    while t > q[0] and any(q):
        #print((t,f,x,q.popleft()))
        q.popleft()
        if len(s) == 0:
            print(-1)
        else:
            print(min(s))
    if not q:
        sys.exit()
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
while q:
    q.pop()
    print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque
    
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e.sort()
q = deque()
for _ in range(p):
    q.append(int(input()))
s=set()
#print(e)
for t,f,x in e:
    while t > q[0]:
        #print((t,f,x,q.popleft()))
        q.popleft()
        if len(s) == 0:
            print(-1)
        else:
            print(min(s))
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
while q:
    q.pop()
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left

n, q = map(int, input().split())
lines = sys.stdin.readlines()
c = []
for line in lines[:n]:
    s, t, x = map(int, line.split())
    c.append((x, s, t))
kkk.sort()
d = list(map(int, lines[n:]))

ans = [-1] * q
skip = [-1] * q
for x, s, t in k:
    ss = bisect_left(d, s - x)
    tt = bisect_left(d, t - x)
    while ss < tt:
        if skip[ss] == -1:
            ans[ss] = x
            skip[ss] = tt
            ss += 1
        else:
            ss = skip[ss]
print(*ans,sep='\n')

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, q = list(map(int, readline().split()))
    event = [0] * (2 * n + q)

    for i in range(n):
        s, t, x = map(int, readline().split())
        event[i * 2] = (s - x, x, 0)
        event[i * 2 + 1] = (t - x, x, 1)

    for i in range(q):
        d = int(input())
        event[2 * n + i] = (d, 0, 2)

    from operator import itemgetter
    import heapq
    event.sort(key=itemgetter(0))
    hq = []
    stop = set()

    for t, x, ev_type in event:
        if ev_type == 0:
            stop.add(x)
            heapq.heappush(hq, x)
        elif ev_type == 1:
            stop.discard(x)
        else:
            if stop:
                while hq:
                    res = heapq.heappop(hq)
                    if res in stop:
                        print(res)
                        break
            else:
                hq.clear()
                print(-1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
N,Q= map(int,input().split())
STX = [list(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

'''
N,Q = 2*10**4,2*10**4
STX = []
order = 10**5
import random
for i in range(N):
    s = random.randint(0, order-1)
    t = random.randint(s+1,order)
    x = random.randint(1,order)
    STX.append([s,t,x])
D = sorted([random.randint(1,order) for i in range(Q)])

'''
inf = 10**12

class SegmentTree:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.l = 2**((N-1).bit_length())
        self.data = [default]*self.l + data + [default]*(self.l-N)
        self.lazy = [default] * (self.l * 2)
        for i in range(self.l-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def get_data(self):
        return self.data[self.l:self.l + self.N]

    def update(self,k):
        if self.lazy[k] == self.default:
            return
        if k < self.l:
            self.lazy[2*k] = self.op(self.lazy[2*k], self.lazy[k])
            self.lazy[2*k+1] = self.op(self.lazy[2*k+1], self.lazy[k])
        self.data[k] = self.op(self.data[k],self.lazy[k])
        self.lazy[k] = self.default

    def set(self,i,j,val):
        def f(self,i,j,k,s,t):
            self.update(k)
            if t <= i or j <= s: # out of range
                return
            if i <= s and t <= j: # included
                self.lazy[k] = val
                self.update(k)
                return
            f(self,i,j,2*k,s,(s+t)//2)
            f(self,i,j,2*k+1,(s+t)//2,t)
            self.data[k] = self.op(self.data[2*k], self.data[2*k+1])
        return f(self,i,j,1,0,self.l)

    def get(self,i,j):
        def g(self,i,j,k,s,t):
            self.update(k)
            if t <= i or j <= s: # out of range
                return self.default # unit element
            if i <= s and t <= j: # has intersection
                return self.data[k]
            # left + right
            return self.op(g(self,i,j,2*k,s,(s+t)//2),g(self,i,j,2*k+1,(s+t)//2,t))
        return g(self,i,j,1,0,self.l)

def segsolve():
    import numpy as np
    sstx = sum([[s-x,t-x] for s,t,x in STX],[])
    sstx = sorted(set(sstx))
    comp = {s:i for i,s in enumerate(sstx)}

    d = np.searchsorted(sstx,D,side='left')

    seg = SegmentTree([inf] * len(sstx), min, inf)
    for s,t,x in STX:
        s = comp[s-x]
        t = comp[t-x]
        seg.set(s,t,x)

    for di in d:
        t = seg.get(di,di+1)
        if t == inf:
            t = -1
        print(t)

def answer():
    import bisect
    from collections import defaultdict,deque
    l = []
    for s,t,x in STX:
        l.append([s-x,True,x])
        l.append([t-x,False,x])
    l.sort()
    m = deque([])
    rm = defaultdict(int)

    i = 0
    for time,add,x in l:
        while i < Q and time > D[i]:
            while m:
                if rm[m[0]] == 0:
                    m.popleft()
                else:
                    print(m[0])
                    break
            else:
                print(-1)
            i += 1
        if add:
            bisect.insort(m,x)
            rm[x] = 1
        else:
            rm[x] = 0

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

answer()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
N,Q= map(int,input().split())
STX = [list(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

'''
N,Q = 2*10**1,2*10**1
STX = []
order = 10**2
import random
for i in range(N):
    s = random.randint(0, order-1)
    t = random.randint(s+1,order)
    x = random.randint(1,order)
    STX.append([s,t,x])
D = sorted([random.randint(1,order) for i in range(Q)])
'''

inf = 10**12

class SegmentTree:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.l = 2**((N-1).bit_length())
        self.data = [default]*self.l + data + [default]*(self.l-N)
        self.lazy = [default] * (self.l * 2)
        for i in range(self.l-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def get_data(self):
        return self.data[self.l:self.l + self.N]

    def update(self,k):
        if self.lazy[k] == self.default:
            return
        if k < self.l:
            self.lazy[2*k] = self.op(self.lazy[2*k], self.lazy[k])
            self.lazy[2*k+1] = self.op(self.lazy[2*k+1], self.lazy[k])
        self.data[k] = self.op(self.data[k],self.lazy[k])
        self.lazy[k] = self.default

    def set(self,i,j,val):
        def f(self,i,j,k,s,t):
            self.update(k)
            if t <= i or j <= s: # out of range
                return
            if i <= s and t <= j: # included
                self.lazy[k] = val
                self.update(k)
                return
            f(self,i,j,2*k,s,(s+t)//2)
            f(self,i,j,2*k+1,(s+t)//2,t)
            self.data[k] = self.op(self.data[2*k], self.data[2*k+1])
        return f(self,i,j,1,0,self.l)

    def get(self,i,j):
        def g(self,i,j,k,s,t):
            self.update(k)
            if t <= i or j <= s: # out of range
                return self.default # unit element
            if i <= s and t <= j: # has intersection
                return self.data[k]
            # left + right
            return self.op(g(self,i,j,2*k,s,(s+t)//2),g(self,i,j,2*k+1,(s+t)//2,t))
        return g(self,i,j,1,0,self.l)

def segsolve():
    import numpy as np
    sstx = sum([[s-x,t-x] for s,t,x in STX],[])
    sstx = sorted(set(sstx))
    comp = {s:i for i,s in enumerate(sstx)}

    d = np.searchsorted(sstx,D,side='left')

    seg = SegmentTree([inf] * len(sstx), min, inf)
    for s,t,x in STX:
        s = comp[s-x]
        t = comp[t-x]
        seg.set(s,t,x)

    for di in d:
        t = seg.get(di,di+1)
        if t == inf:
            t = -1
        print(t)

def answer():
    import bisect
    l = []
    for s,t,x in STX:
        l.append([s-x,True,x])
        l.append([t-x,False,x])
    l.sort()
    m = []
    i = 0
    for time,add,x in l:
        while time > D[i]:
            if m:
                print(m[0])
            else:
                print(-1)
            i += 1
        if add:
            bisect.insort(m,x)
        else:
            m.remove(x)
    while i < Q:
        print(-1)
        i += 1


answer()

Submission status: Runtime Error

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

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

def main():
    mod=10**9+7
    import bisect

    """
    各工事場所について，
    Dがどのレンジなら引っかかるかを記録しておく．
    最初全部のDに関して，infまで行けるものとして，
    Xが大きい順に工事区間を見て，引っかかるならば区間更新
    """

    
    N,Q=MI()
    xst2=[]#x,ごとに，Dがどの範囲なら引っかかるか(s~t)
    for i in range(N):
        s,t,x=MI()
        xst2.append([x,s-x,t-x])
    xst2.sort(reverse=True)
    
    
    #遅延セグ木##
    INF=10**10
    LV = Q.bit_length()
    N0 = 2**LV
    data = [INF]*(2*N0)
    lazy = [None]*(2*N0)

    def gindex(l, r):
        L = l + N0; R = r + N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1

    def propagates(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if v is None:
                continue
            lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
            lazy[i-1] = None

    def update(l, r, x):
        *ids, = gindex(l, r)
        propagates(*ids)

        L = N0 + l; R = N0 + r
        while L < R:
            if R & 1:
                R -= 1
                lazy[R-1] = data[R-1] = x
            if L & 1:
                lazy[L-1] = data[L-1] = x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            data[i-1] = min(data[2*i-1], data[2*i])

    def query(l, r):
        propagates(*gindex(l, r))
        L = N0 + l; R = N0 + r

        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
    ###
    
    
    
    D=[0]*Q
    for i in range(Q):
        D[i]=I()
        
        

    #1~10**9は大きいので，Dに与えられた値のみを見る，
    
    for i in range(N):
        x,s,t=xst2[i][0],xst2[i][1],xst2[i][2]
        nums=bisect.bisect_left(D,s)
        numt=bisect.bisect_left(D,t)
        update(nums,numt,x)
        
    for i in range(Q):
        ans=query(i,i+1)
        if ans==INF:
            print(-1)
        else:
            print(ans)
        
    
        

main()

Submission status: Runtime Error

Solution code:
# 二部探索で決めていく。dpですでに見られたかどうかは把握
from bisect import bisect_left
n,q  = map(int, input().split())
imos = [0] * n
roadworks = []
for i in range(n):
    s,t,x = map(int, input().split())
    roadworks.append((s,t,x))
roadworks.sort()

ds = [(int(input()),i) for i in range(q)]  
ds.sort()
ix = [d[1] for d in ds]
ds = [d[0] for d in ds]
xs = [-1]*(n+10)
for s,t,x in roadworks:
    # print(s-x,t-x)
    l = bisect_left(ds,s-x-0.5)
    r = bisect_left(ds,t-x-0.5)
    for i in range(l,r):
        if xs[i] != -1:continue
        xs[i] = x
    # print("index",l,r)

for i in range(q):
    print(xs[i])

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect_right

class LazySegmentTree:
    INF = float("inf")

    def __init__(self, n):
        self.n = 1 << (n-1).bit_length()
        self.data = [self.INF] * (self.n*2)
        self.lazy = [None] * (self.n*2)
    
    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.n+i] = x
        for i in range(self.n-1, 0, -1):
            self.data[i] = min(self.data[i*2], self.data[i*2+1])
        
    def query(self, l, r):
        self.__propagate(self.__getidx(l, r))

        l += self.n; r += self.n 
        res = self.INF
        while l < r:
            if l & 1:
                res = min(res, self.data[l])
                l += 1
            if r & 1:
                res = min(res, self.data[r-1])
            l >>= 1; r >>= 1
        return res
    
    def update(self, l, r, x):
        idx = self.__getidx(l, r)
        self.__propagate(idx)

        l += self.n; r += self.n 

        while l < r:
            if l & 1:
                self.data[l], self.lazy[l] = x, x
                l += 1
            if r & 1:
                self.data[r-1], self.lazy[r-1] = x, x
            l >>= 1; r >>= 1
    
        for i in idx:
            self.data[i] = min(self.data[i*2], self.data[i*2+1])

    def __getidx(self, l, r):
        l += self.n; r += self.n 
        lm = l // ((l & -l) << 1)
        rm = r // ((r & -r) << 1)
        res = []
        while l < r:
            if l <= lm: res.append(l)
            if r <= rm: res.append(r)
            l >>= 1; r >>= 1
        while l:
            res.append(l)
            l >>= 1
        return res
    
    def __propagate(self, idx):
        for i in reversed(idx):
            val = self.lazy[i]
            if val is None: continue
            self.lazy[i*2] = val; self.lazy[i*2+1] = val
            self.data[i*2] = val; self.data[i*2+1] = val
            self.lazy[i] = None

n, q = map(int, input().split())
query = [None] * n
for i in range(n):
    s, t, x = map(int, input().split())
    query[i] = s-x, t-x, x
d = [int(input()) for _ in range(q)]
lst = LazySegmentTree(q)

query.sort(key=lambda x: x[2], reverse=True)

for l, r, x in query:
    lst.update(bisect_left(d, l), bisect_left(d, r), x)

for i in range(q):
    ans = lst.query(i, i+1)
    print(-1 if ans == float("inf") else ans)

Submission status: Runtime Error

Solution code:
import heapq
def resolve():
    n, q = map(int, input().split())
    koji = []
    a = []
    j = 0
    for i in range(n):
        s, t, x = map(int, input().split())
        koji.append([s - x, 1, x])
        koji.append([t - x, -1, x])
    m = len(koji)
    koji.sort()
    d = [int(input()) for _ in range(q)]
    for i in range(q):
        while d[i] >= koji[j][0]:
            if koji[j][1] == 1:
                heapq.heappush(a, koji[j][2])
            else:
                a.remove(koji[j][2])
            if j == m - 1:
                break
            else:
                j += 1

        if len(a) == 0:
            print(-1)
        else:
            print (a[0])
resolve()

Submission status: Runtime Error

Solution code:
def resolve():
    n, q = map(int, input().split())
    koji = []
    a = []
    j = 0
    for i in range(n):
        s, t, x = map(int, input().split())
        koji.append([s - x, 1, x])
        koji.append([t - x, -1, x])
    m = len(koji)
    koji.sort()
    d = [int(input()) for _ in range(q)]
    for i in range(q):
        while d[i] >= koji[j][0]:
            if koji[j][1] == 1:
                heappush(a,koji[j][2])
            else:
                a.remove(koji[j][2])
            if j == m - 1:
                break
            else:
                j += 1

        if len(a) == 0:
            print(-1)
        else:
            print(heappop(a))
resolve()

Submission status: Runtime Error

Solution code:
def resolve():
    n, q = map(int, input().split())
    koji = []
    a = []
    j=0
    for i in range(n):
        s, t, x = map(int, input().split())
        koji.append([s-x,1,x])
        koji.append([t-x,-1,x])
    m=len(koji)
    koji.sort()
    d = [int(input()) for _ in range(q)]
    for i in range(q):
       while d[i] >= koji[j][0]:
           if koji[j][1]==1:
               a.append(koji[j][2])
           else:
               a.remove(koji[j][2])
           if j == m-1:
             break
           else:
               j+=1

       if len(a)==0:
           print(-1)
       else:
           print(min(a))
resolve()

Submission status: Runtime Error

Solution code:
def resolve():
    n, q = map(int, input().split())
    s = [0] * n
    t = [0] * n
    x = [0]*n
    koji = []
    a = []
    j=0
    for i in range(n):
        s[i], t[i], x[i] = map(int, input().split())
        koji.append([s[i]-x[i],1,x[i]])
        koji.append([t[i]-x[i],-1,x[i]])
    m=len(koji)
    koji.sort()
    d = [int(input()) for _ in range(q)]
    for i in range(q):
       while d[i] >= koji[j][0]:
           if koji[j][1]==1:
               a.append(koji[j][2])
           else:
               a.remove(koji[j][2])
           if j == m-1:
             break
           else:
               j+=1

       if len(a)==0:
           print(-1)
       else:
           print(min(a))
resolve()

Submission status: Runtime Error

Solution code:
def resolve():
    n, q = map(int, input().split())
    s = [0] * n
    t = [0] * n
    x = [0]*n
    koji = []
    a = set()
    j=0
    for i in range(n):
        s[i], t[i], x[i] = map(int, input().split())
        koji.append([s[i]-x[i],1,x[i]])
        koji.append([t[i]-x[i],-1,x[i]])
    m=len(koji)
    koji.sort()
    d = [int(input()) for _ in range(q)]
    for i in range(q):
       while d[i] >= koji[j][0]:
           if koji[j][1]==1:
               a.add(koji[j][2])
           else:
               a.remove(koji[j][2])
           if j == m-1:
             break
           else:
               j+=1

       if len(a)==0:
           print(-1)
       else:
           print(min(a))
resolve()

Submission status: Runtime Error

Solution code:
 n, q = map(int, input().split())
    s = [0] * n
    t = [0] * n
    x = [0] * n
    koji = [[0 for i in range(3)] for j in range(n)]
    for i in range(n):
        s[i], t[i], x[i] = map(int, input().split())
        koji[i][0] = x[i]
        koji[i][1]=s[i]-x[i]
        koji[i][2]=t[i]-x[i]
    koji.sort()
    d = [int(input()) for _ in range(q)]
    for i in range(q):
        for j in range(n):
            if d[i]>=koji[j][1] and d[i]<koji[j][2]:
                print(koji[j][0])
                break
            elif j==n-1:
                print(-1)

Submission status: Runtime Error

Solution code:
N,Q = map(int, input().split())
evt = []
for _ in range(N):
    S,T,X = map(int, input().split())
    s = max(S-X-0.5,0)
    t = max(T-X-0.5,0)
    evt.append([s,0.1,X])
    evt.append([t,0,X])

evt.sort(key=lambda x: x[0]+x[1])
Ds = [int(input()) for _ in range(Q)]
lD = len(Ds)
stack = set()
itr = 0
for s,b,x in evt:
    for i in range(itr,lD):
        if Ds[i] > s:
            break
    if b == 0.1:
        stack.add(x)
    else:
        stack.remove(x)
    if itr < i:
        sl = list(stack)
        t = -1 if len(sl) == 0 else sl[0]
        for _ in range(i - itr):
            print(t)
        itr = i

Submission status: Runtime Error

Solution code:
N,Q = map(int, input().split())
evt = []
for _ in range(N):
    S,T,X = map(int, input().split())
    s = max(S-X,0)
    t = max(T-X,0)
    evt.append([s,1,X])
    evt.append([t,0,X])

evt.sort(key=lambda x: x[0]+x[1])
for _ in range(Q):
    D = int(input())
    stack = {}
    for s,b,x in evt:
        if D < s:
            break
        if b == 1:
            stack[x] = True
        else:
            del stack[x]
    sk = stack.keys()
    if len(sk) == 0:
        print(-1)
    else:
        print(sorted(sk)[0])

Submission status: Runtime Error

Solution code:
import os

l = [-1] * 10**8
N,Q = map(int, input().split())
for _ in range(N):
    S,T,X = map(int, input().split())
    s = max(S-X,0)
    t = max(T-X,0)
    for i in range(t-s):
        if l[s+i] == -1 or l[s+i] > X:
            l[s+i] = X

for _ in range(Q):
    D = int(input())
    print(l[D])

os._exit(0)

Submission status: Runtime Error

Solution code:
l = [-1] * 10**8
N,Q = map(int, input().split())
for _ in range(N):
    S,T,X = map(int, input().split())
    s = max(S-X,0)
    t = max(T-X,0)
    for i in range(t-s):
        if l[s+i] == -1 or l[s+i] > X:
            l[s+i] = X

for _ in range(Q):
    D = int(input())
    print(l[D])

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

stx=[[int(x) for x in readline().split()] for _ in range(n)]
event=[]
for s,t,x in stx:
    event.append((s-x,1,x))
    event.append((t-x,-1,x))

for i in range(q):
    event.append((int(input()),2,i))
event.sort()

ans=[0]*q

stop=set()
hq=[]
for t,op,x in event:
    if op==1:
        heappush(hq,x)
        stop.add(x)
    elif op==-1:
        stop.remove(x)

    else:
        while hq and hq[0] not in stop:
            heappop(hq) 
        ans[x]=hq[0] if hq else -1
    
for x in ans:
    print(x)

Submission status: Runtime Error

Solution code:
def main():
    from heapq import heappush, heappop
    import sys
    sys.setrecursionlimit(10 ** 7)
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines


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

    stx=[[int(x) for x in readline().split()] for _ in range(n)]
    event=[]
    for s,t,x in stx:
        event.append((s-x,1,x))
        event.append((t-x,-1,x))

    for i in range(q):
        event.append((int(input()),2,i))
    event.sort()

    ans=[0]*q

    stop=set()
    hq=[]
    for t,op,x in event:
        if op==1:
            heappush(hq,x)
            stop.add(x)
        elif op==-1:
            stop.remove(x)

        else:
            while hq and hq[0] not in stop:
                heappop(hq) 
            ans[x]=hq[0] if hq else -1
        
    for x in ans:
        print(x)

main()

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,Q = LI()
    q = LIR(n)
    q.sort(key = lambda x:x[2])
    d = IR(Q)
    ans = [-1]*Q
    f = [0]*Q
    for s,t,x in q:
        l = bisect.bisect_left(d,s-x)
        r = bisect.bisect_left(d,t-x)
        while l < r:
            while ans[l] != -1:
                l = f[l]
            if r <= l:
                break
            ans[l] = x
            f[l] = r
            l += 1
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import sys
#import numpy as np
import bisect
sys.setrecursionlimit(10 ** 7)

# TLE
# PyPy3 (2.4.0) 2112 ms

N, Q = map(int, input().split())
STX = []
for _ in range(N):
    s, t, x = map(int, input().split())
    STX.append((s, t, x))

PEOPLE = []
for _ in range(Q):
    d = int(input())
    PEOPLE.append(d)

ans = [-1] * Q

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

for s, t, x in STX:
    if len(PEOPLE) == 0:
        break

    i = bisect.bisect_left(PEOPLE, s - x)
    j = bisect.bisect_left(PEOPLE, t - x)

    if i == j:
        continue

    use = [PEOPLE[x] for x in range(i, j)]

    for k in use:
        if ans[k] == -1:
            ans[k] = x

    del PEOPLE[i:j]


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

Submission status: Runtime Error

Solution code:
import heapq
N, Q = (int(i) for i in input().split())
L = [0] * 2 * N
for i in range(N):
    S, T, X = (int(i) for i in input().split())
    L[2 * i] = (S-X, X, 1)
    L[2 * i + 1] = (T-X, X, 0)

L.sort(reverse=True)

Xs = set([])
XH = []
heapq.heapify(XH)
for i in range(Q):
    D = int(input())
    ans = 0
    while True:
        if L:
            t, X, f = L.pop()
            if t <= D:
                if f == 1:
                    Xs.add(X)
                    heapq.heappush(XH, X)
                else:
                    Xs.remove(X)
            else:
                L.append((t, X, f))
                break
        else:
            break
    if Xs:
        while True:
            X = heapq.heappop(XH)
            if X in Xs:
                print(X)
                break
    else:
        print("-1")

Submission status: Runtime Error

Solution code:
import heapq
def main():
    N, Q = map(int, input().split())
    ls = []
    lt = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        ls.append((s-x, x))
        lt.append((t-x, x))
    heapq.heapify(ls)
    heapq.heapify(lt)
    dl = set()
    m = 0
    for i in range(Q):
        d = int(input())
        if len(ls) > 0 and ls[0][0] > d:
            while len(lt) > 0 and lt[0][0] <= d:
                t, x = heapq.heappop(lt)
                dl.remove(x)
        elif len(ls) > 0:
            while len(lt) > 0 and lt[0][0] <= ls[0][0]:
                t, x = heapq.heappop(lt)
                dl.remove(x)
            while len(ls) > 0 and ls[0][0] <= d:
                s, x = heapq.heappop(ls)
                dl.add(x)
                while len(lt) > 0 and lt[0][0] <= s:
                    t, x = heapq.heappop(lt)
                    dl.remove(x)
            while len(lt) > 0 and lt[0][0] <= d:
                t, x = heapq.heappop(lt)
                dl.remove(x)
        else:
            while len(lt) > 0 and lt[0][0] <= d:
                t, x = heapq.heappop(lt)
                dl.remove(x)
        if not dl:
            print('-1')
        else:
            if m not in dl:
                m = min(dl)
            print(min(dl))
main()

Submission status: Runtime Error

Solution code:
import heapq
def main():
    N, Q = map(int, input().split())
    ls = []
    lt = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        ls.append((s-x, x))
        lt.append((t-x, x))
    heapq.heapify(ls)
    heapq.heapify(lt)
    dl = set()
    for i in range(Q):
        d = int(input())
        while len(lt) > 0 and lt[0][0] <= d:
            t, x = heapq.heappop(lt)
            dl.remove(x)
        while len(ls) > 0 and ls[0][0] <= d:
            s, x = heapq.heappop(ls)
            dl.add(x)
        if not dl:
            print('-1')
        else:
            print(min(dl))
main()

Submission status: Runtime Error

Solution code:
import heapq


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

event_list.sort()
event_list.append([10**10, 1, 10**10])
i = 0
x_set = set()
x_list = []
time = 0
for q in range(Q):
  d = int(input())
  while time <= d:
    time, event, x = event_list[i]
    if time <= d:
      if event == 1:
        x_set.add(x)
        heapq.heappush(x_list, x)
      else:
        x_set.remove(x)
      i += 1
  
  while x_list and x_list[0] not in x_set:
    _ = heapq.heappop(x_list)
  if x_list:
    prin(x_list[0])
  else:
    print(-1)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(vec) vec.begin(), vec.end()

using namespace std;

typedef struct e {
	double t;
	int m;
	int x;
}e;

bool cmp(const e& a, const e& b) { return a.t < b.t; }

int main() {
	int N, Q;
	cin >> N >> Q;

	vector<e> event;
	rep(i, N) {
		int s, t, x;
		cin >> s >> t >> x;
		event.push_back(e{s-x-0.5, 0, x});
		event.push_back(e{t-x-0.5, 1, x});
	}

	rep(i, Q) {
		double d;
		cin >> d;
		event.push_back(e{d, 2, 0});
	}

	sort(all(event), cmp);

	vector<int> d;

	for (auto eve : event) {
		if (eve.m == 0) {
			if (d.empty()) d.push_back(eve.x);
			else d.insert(lower_bound(all(d), eve.x), eve.x);
		}
		else if (eve.m == 1) d.erase(lower_bound(all(d), eve.x));
		else {
			if (!d.empty()) cout << d[0] << endl;
			else cout << -1 << endl;
			Q--;
			if (Q == 0) return 0;
		}
	}

	return 0;

}

Submission status: Runtime Error

Solution code:
import numpy as np
n, q = list(map(int, input().split()))
eventList = []

for i in range(n):
    stop = list(map(int, input().split()))
    eventList.append([stop[0] - stop[2], 1, stop[2]])
    eventList.append([stop[1] - stop[2], -1, stop[2]])


for i in range(q):
    departure = int(input())
    eventList.append([departure, 0, i])

eventList.sort(key=lambda x: x[0])

ans = []
stopArea = np.array([])
for event in eventList:
    if event[1] == 1:
        stopArea.append(event[2])
    elif event[1] == -1:
        stopArea.remove(event[2])
    else:
        if len(stopArea) == 0:
            ans.append(-1)
        else:
            ans.append(np.min(stopArea))

for a in ans:
    print(a)