Problem: There is an infinitely long street that runs west to east, which we consider as a number line.  There are N roadworks scheduled on this street. The i-th roadwork blocks the point at coordinate X_i from time S_i - 0.5 to time T_i - 0.5.  Q people are standing at coordinate 0. The i-th person will start the coordinate 0 at time D_i, continue to walk with speed 1 in the positive direction and stop walking when reaching a blocked point.  Find the distance each of the Q people will walk.

Submission attempts (in order):
from bisect import*
import sys;input=sys.stdin.readline

def doevent(lis):
    global stop
    a,b=lis
    if b>=0:
        if stop=={-1}:
            stop=set()
        stop.add(b)
    else:
        if -b in stop:
            stop.remove(-b)
        if stop==set():
            stop={-1}
    return min(stop)


def main():
    n,q=map(int,input().split())
    event=[]
    stop=set([-1])
    for i in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,x))
        event.append((t-x,-x))
    event.sort(key=lambda x:x[0])
    minlist=[doevent(i)for i in event] 

    for i in range(q):
        print(minlist[bisect_right(event,(int(input()),10**9))-1])
if __name__ == '__main__':
    main()

import sys;input=sys.stdin.readline
from bisect import*
from collections import deque

n,q=map(int,input().split())
event=deque([])
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:
        if l[2] in stopped:
            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


import sys;input=sys.stdin.readline

def main():
    n,q=map(int,input().split())
    event=[]
    stop=set()
    for i in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,x))
        event.append((t-x,-x))
    for i in range(q):
        event.append((int(input()),str(i)))
    
    event.sort()
    ans=[-1]*q
    minstop=float("inf")
    for t,x in event:
        if type(x)==str:
            ans[int(x)]=str(minstop)
            continue
        elif x>=0:
            stop.add(x)
        elif x<0:
            stop.remove(-x)
        if minstop!=x:
            minstop=min(stop or [-1])
    print("\n".join(ans))
    
if __name__ == '__main__':
    main()


import sys;input=sys.stdin.readline
from bisect import*
from collections import deque

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

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

import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))
    
event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop
        
print('\n'.join(map(str, ans)))

Verdicts: Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Accepted