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
inf = float('inf')
mod = 10**9+7


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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

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

    event.sort(key=lambda x: x[0])
    occur = set()
    occur_priority = []
    for e in event:
        if e[1] == 1:
            occur.add(e[2])
            heapq.heappush(occur_priority, e[2])
        elif e[1] == -1:
            if e[2] in occur:
                occur.remove(e[2])
        # クエリ
        elif e[1] == 0:
            if occur:
                while 1:
                    poped = heapq.heappop(occur_priority)
                    if poped in occur:
                        break
                print(poped)
            else:
                print(-1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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

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

    event.sort(key=lambda x: x[0])
    occur = set()
    occur_priority = []
    for e in event:
        if e[1] == 1:
            occur.add(e[2])
            heapq.heappush(occur_priority, e[2])
        elif e[1] == -1:
            occur.remove(e[2])
        # クエリ
        elif e[1] == 0:
            if occur:
                while 1:
                    poped = heapq.heappop(occur_priority)
                    if poped in occur:
                        break
                print(poped)
            else:
                print(-1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


def main():
    from collections import defaultdict
    N, Q = MI()
    event = []
    hash = defaultdict(int)
    for _ in range(N):
        s, t, x = MI()
        event.append((s - x-0.5, 1, x))
        event.append((t - x-0.5, -1, x))
        hash[x] = 0

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

    event.sort(key=lambda x: x[0])
    occur = set()
    for e in event:
        if e[1] == 1:
            occur.add(e[2])
        elif e[1] == -1:
            occur.remove(e[2])
        # クエリ
        elif e[1] == 0:
            if occur:
                print(min(occur))
            else:
                print(-1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


def main():
    from collections import defaultdict
    N, Q = MI()
    event = []
    hash = defaultdict(int)
    for _ in range(N):
        s, t, x = MI()
        event.append((s - x, 1, x))
        event.append((t - x, -1, x))
        hash[x] = 0

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

    event.sort(key=lambda x: x[0])
    occur = set()
    for e in event:
        if e[1] == 1:
            occur.add(e[2])
        elif e[1] == -1:
            occur.remove(e[2])
        # クエリ
        elif e[1] == 0:
            if occur:
                print(min(occur))
            else:
                print(-1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
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(key=lambda x:x[0])
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)))

Submission status: Runtime Error

Solution code:
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(key=lambda x:x[0])
    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 and len(stop)>0:
            stop.remove(-x)
        if minstop!=x:
            minstop=min(stop or [-1])
    print("\n".join(ans))
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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()),"q"))
    
    event.sort(key=lambda x:x[0])
    ans=[]
    minstop=float("inf")
    for t,x in event:
        if type(x)==str:
            ans.append(str(minstop))
            continue
        elif x>=0:
            stop.add(x)
        elif x<0 and len(stop)>0:
            stop.remove(-x)
        if minstop!=x:
            minstop=min(stop or [-1])
    print("\n".join(ans))
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
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()),"q"))
    
    event.sort(key=lambda x:x[0])
    ans=[]
    minstop=float("inf")
    for t,x in event:
        if type(x)==str:
            ans.append(str(minstop))
        elif x>=0:
            stop.add(x)
        elif x<0 and len(stop)>0:
            stop.remove(-x)
        if minstop!=x:
            minstop=min(stop or [-1])
    print("\n".join(ans))
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, merge
from collections import defaultdict
import sys
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    events = []
    for _ in range(N):
        s, t, x = map(int, line_input())
        events.append((s-x, 1, x))
        events.append((t-x, -1, x))
    for _ in range(Q):
        d = int(single_input)
        events.append((d, 2, d))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    ans = ''
    for _, flag, coord in events:
        if flag == 1:
            heappush(constructions, coord)
            under_construction[coord] = True
        elif flag == -1:
            under_construction[coord] = False
        else:
            while constructions:
                x = heappop(constructions)
                if under_construction[x]: # x is the minimum coordinate under construction
                    heappush(constructions, x)
                    ans += str(x) + '\n'
                    break
            else: # no constructions
                ans += '-1\n'
    print(ans)
    
if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
from bisect import*
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))
    event.sort(key=lambda x:x[0])
    time=[]
    minstop=float("inf")
    for t,x in event:
        if x>=0:
            stop.add(x)
        elif x<0:
            stop.remove(-x)
        
        if minstop!=x:
            minstop=min(stop or [-1])
        time.append(minstop)
    
    for i in range(q):
        print(time[bisect_right( event,(int(input()),float("inf")) )-1])
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from bisect import*
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))
    event.sort(key=lambda x:x[0])
#    print(event)
    time=[]
    for t,x in event:
#        print(stop)
        if x>=0:
            stop.add(x)
        elif x<0:
            stop.remove(-x)
        time.append(min(stop or [-1]))
    
    for i in range(q):
        print(time[bisect_right( event,(int(input()),float("inf")) )-1])
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, merge
from collections import defaultdict

def solve():
  N, Q = map(int, input().split())
  events = []
  for _ in range(N):
    s, t, x = map(int, input().split())
    events.append((s-x, 1, x))
    events.append((t-x, -1, x))
    events = sorted(events)

    constructions = []
    under_construction = defaultdict(bool)
    i = 0
    for _ in range(Q):
      d = int(input())
      while i < 2*N and events[i][0] <= d:
        if events[i][1] > 0:
          heappush(constructions, events[i][2])
          under_construction[events[i][2]] = True
        else:
          under_construction[events[i][2]] = False
        i += 1
      while constructions:
      	x = heappop(constructions)
        if under_construction[x]: # x is the minimum coordinate under construction
          heappush(constructions, x)
          print(x)
          break
      else: # no constructions
        print(-1)
        
if __name__ == "__main__":
  solve()

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, merge

N, Q = map(int, input().split())
events = []
for _ in range(N):
    s, t, x = map(int, input().split())
    events.append((s-x, 1, x))
    events.append((t-x, -1, x))
events = sorted(events)
constructions = []
i = 0
for _ in range(Q):
    d = int(input())
    while i < 2*N and events[i][0] <= d:
        if events[i][1] > 0:
            heappush(constructions, events[i][2])
        else:
            temp = []
            while constructions[0] != events[i][2]:
                heappush(temp, heappop(constructions))
            heappop(constructions)
            constructions = list(merge([temp, constructions]))
        i += 1
    print(constructions[0] if constructions else -1)

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, merge

N, Q = map(int, input().split())
events = []
for _ in range(N):
    s, t, x = map(int, input().split())
    events.append((s-x, 1, x))
    events.append((t-x, -1, x))
events = sorted(events)
constructions = []
i = 0
for _ in range(Q):
    d = int(input())
    while i < 2*N and events[i][0] <= d:
        if events[i][1] > 0:
            heappush(constructions, events[i][2])
        else:
            temp = []
            while constructions[0] != events[i][2]:
                heappush(temp, heappop(constructions))
            heappop(constructions)
            merge([temp, constructions])
        i += 1
    print(constructions[0] if constructions else -1)

Submission status: Runtime Error

Solution code:
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] #時間をindexとしたminlist

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

Submission status: Runtime Error

Solution code:
import sys, collections, heapq
def single_input(F): return F.readline().strip("\n")
def line_input(F): return F.readline().strip("\n").split()

def solve():
    F = sys.stdin
    N, Q = map(int, line_input())
    event = []
    for i in range(N):
        s, t, x = map(int, line_input())
        event.append((s-x, 1, x))
        event.append((t-x,-1, x))
    for i in range(Q):
        d = int(single_input())
        event.append((d, 2, d))
    event.sort()
    candidate = []
    heapq.heapify(candidate)
    stop = collections.defaultdict(int)
    ans = ""
    for time, parameter, co in event:
        if parameter == 1:
            heapq.heappush(candidate, co)
            stop[co] += 1
        elif parameter == -1:
            stop[co] -= 1
        else:
            while candidate:
                x = heapq.heappop(candidate)
                if stop[x] > 0:
                    heapq.heappush(candidate, x)
                    ans += str(x) + "\n"
                    break
            else: ans += "-1\n"
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    event = []
    for i in range(N):
        s, t, x = map(int, line_input())
        event.append((max(s-x, 0), 1, x))
        event.append((max(t-x, 0), -1, x))
    for i in range(Q):
        d = int(single_input())
        event.append((d, 2, d))
    event.sort()
    stop = []
    ans = ""
    for time, parameter, co in event:
        if parameter == 1: stop.append(co)
        elif parameter == -1: stop.remove(co)
        else:
            if stop:
                stop.sort()
                ans += str(stop[0]) + "\n"
            else: ans += "-1\n"
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    event = []
    for i in range(N):
        s, t, x = map(int, line_input())
        event.append((max(s-x, 0), 1, x, i))
        event.append((max(t-x, 0), -1, x, i))
    for i in range(Q):
        d = int(single_input())
        event.append((d, 2, 0, 0))
    event.sort()
    stop = []
    heapq.heapify(stop)
    ans = ""
    for time, parameter, co, ci in event:
        if parameter == 1: heapq.heappush(stop, (co, i))
        elif parameter == -1: stop.remove((co, i))
        else:
            if stop: ans += str(stop[0][0]) + "\n"
            else: ans += "-1\n"
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    event = []
    for i in range(N):
        s, t, x = map(int, line_input())
        event.append((max(s-x, 0), 1, x))
        event.append((max(t-x, 0), -1, x))
    for i in range(Q):
        d = int(single_input())
        event.append((d, 2, 0))
    event.sort()
    stop = []
    heapq.heapify(stop)
    ans = ""
    for time, parameter, co in event:
        if parameter == 1: heapq.heappush(stop, co)
        elif parameter == -1: stop.remove(co)
        else:
            if stop: ans += str(stop[0]) + "\n"
            else: ans += "-1\n"
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

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

  L = []
  for s, t, x in STX:
    L.append((x, s - x, t - x))

  L.sort(key = lambda x: x[1])
  q = []
  cnt = 0
  push = heapq.heappush
  pop = heapq.heappop
  t = []
  for i in range(Q):
    while cnt < len(L) and D[i] >= L[cnt][1]:
      if t != []:
        t = []
        push(q, t)
      push(q, L[cnt])
      cnt += 1
    if t != [] and t[2] > D[i]:
      print(t[0])
    else:
      while q != []:
        t = pop(q)
        if t[2] > D[i]:
          print(t[0])
          break
      else:
        t = []
        print(-1)

main()

Submission status: Runtime Error

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

  L = []
  for s, t, x in STX:
    L.append((x, s - x, t - x))

  L.sort(key = lambda x: x[1])
  q = []
  cnt = 0
  push = heapq.heappush
  pop = heapq.heappop
  t = []
  for i in range(Q):
    while cnt < len(L) and D[i] >= L[cnt][1]:
      if t != []:
        push(t)
      push(q, L[cnt])
      cnt += 1
    if t != [] and t[2] > D[i]:
      print(t[0])
    else:
      while q != []:
        t = pop(q)
        if t[2] > D[i]:
          print(t[0])
          break
      else:
        t = []
        print(-1)

main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = list(map(int, readl().rstrip().split())) for _ in range(N)]
  Dn = [None for _ in range(Q+1)]
  for i in range(Q):
    Dn[i] = int(readl().rstrip())
  Dn[Q] = 10**10
  ans = []

  for s,t,x in sorted(STX,key=lambda x:x[2]):
    l = r = bisect_left(Dn,s-x)
    t -= x
    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,Q


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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = list(map(int, readl().rstrip().split())) for _ in range(N)]
  Dn = [None]*(Q+1)
  for i in range(Q):
    Dn[i] = int(readl().rstrip())
  Dn[Q] = 10**10
  ans = []

  for s,t,x in sorted(STX,key=lambda x:x[2]):
    l = r = bisect_left(Dn,s-x)
    t -= x
    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,Q


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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = list(map(int, readl().rstrip().split())) for _ in range(N)]
  Dn = [None]*(Q+1)
  for i in range(Q):
    Dn[i] = int(readl().rstrip())
    Dn[Q] = [10**10]
  ans = []

  for s,t,x in sorted(STX,key=lambda x:x[2]):
    l = r = bisect_left(Dn,s-x)
    t -= x
    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,Q


if __name__ == "__main__":
  ans,n = main()
  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
import numpy as np


readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = [list(map(int, readl().rstrip().split())) for _ in range(N)]
  Dn = np.asarray([int(readl().rstrip()) for _ in range(Q)] + [10**10])
  ans = []

  for s,t,x in sorted(STX,key=lambda x:x[2]):
    l = bisect_left(Dn,s-x)
    t -= x
    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,Q


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

Submission status: Runtime Error

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

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])
    try:
        while i==query[c]:
            print(min(stopped))
            c+=1
    except:
        break

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
        if c==q-1:
            break

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
        if c==q:
            break

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
        if c==q:
            break
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={-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):
    doevent(event[i])
    while i==query[c]:
        print(min(stopped))
        c+=1
for i in range(query.count(2*n)):
    print(-1)