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

import sys
input = sys.stdin.readline

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  q.append((s-x,1,x)) 
  q.append((t-x,0,x)) 

for i in range(Q):
  d = int(input())
  q.append((d,2,i))
answer = [-1]*Q

se = set() 

q.sort()

for a,c,b in q:
  if not c:
    se.remove(b)
  elif c&1:
    se.add(b)
  #else:
  #  if se:
  #    answer[b] = min(se)

print('\n'.join(map(str,answer)))



import sys
input = sys.stdin.readline
from heapq import heappush,heappop

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  heappush(q,(s-x,1,x)) 
  heappush(q,(t-x,0,x)) 

for i in range(Q):
  d = int(input())
  heappush(q,(d,2,i))
answer = [-1]*Q

se = []
remove_task = []

while q:
  a,c,b = heappop(q)
  if not c:
    heappush(remove_task,b)
  elif c&1:
    heappush(se,b)
  #else:
  #  while remove_task and (se[0] == remove_task[0]):
  #    heappop(se)
  #    heappop(remove_task)
  #  if se:
  #    answer[b] = se[0]
  #print(a,c,b,se,remove_task)
print('\n'.join(map(str,answer)))



import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) 
  task.append((s-x,1,x)) 

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) 
answer = [-1]*Q

task.sort()


se = set()
se_sort = [] 


for a,b,c in task:
  if not b: # b == 0
    se.remove(c)
  elif b&1: # b == 1
    se.add(c)
    heappush(se_sort,c)
  else: # b == 2
    while se_sort and se_sort[0] in se:
      heappop(se_sort)
    answer[c] = se_sort[0] if se_sort else -1

print('\n'.join(map(str,answer)))



import sys
input = sys.stdin.readline
from heapq import heappush,heappop

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  heappush(q,(s-x,1,x)) 
  heappush(q,(t-x,0,x)) 
  
D = [int(input()) for _ in range(Q)]
for i,d in enumerate(D):
  heappush(q,(d,2,i))
answer = [-1]*Q

se = set() 

while q:
  a,c,b = heappop(q)
  if c == 2: 
    if se:
      #answer[b] = min(se)
  elif c == 1:
    se.add(b)
  elif c == 0:
    se.remove(b)

    
for x in answer:
  print(x)



import sys
input = sys.stdin.readline
from heapq import heappush,heappop

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  heappush(q,(s-x,1,x)) 
  heappush(q,(t-x,0,x)) 
  
D = [int(input()) for _ in range(Q)]
for i,d in enumerate(D):
  heappush(q,(d,2,i))
answer = [-1]*Q

se = set() 

while q:
  a,c,b = heappop(q)
  if c == 2: 
    if se:
      pass
      #answer[b] = min(se)
  elif c == 1:
    se.add(b)
  elif c == 0:
    se.remove(b)

    
for x in answer:
  print(x)



import sys
input = sys.stdin.readline
from heapq import heappush,heappop

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  heappush(q,(s-x,1,x)) 
  heappush(q,(t-x,0,x)) 

for i in range(Q):
  d = int(input())
  heappush(q,(d,2,i))
answer = [-1]*Q

se = set() 

while q:
  a,c,b = heappop(q)
  if not c:
    se.remove(b)
  elif c&1:
    se.add(b)
  #else:
  #  if se:
  #    answer[b] = min(se)

print('\n'.join(map(str,answer)))



import sys
input = sys.stdin.readline
from heapq import heappush,heappop

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  heappush(q,(s-x,1,x)) 
  heappush(q,(t-x,0,x)) 

for i in range(Q):
  d = int(input())
  heappush(q,(d,2,i))
answer = [-1]*Q

se = set() 

while q:
  a,c,b = heappop(q)
  if not c:
    se.remove(b)
  elif c&1:
    se.add(b)
  else:
    if se:
      answer[b] = 0#min(se)

print('\n'.join(map(str,answer)))



import sys
input = sys.stdin.readline
from heapq import heappush,heappop

N,Q = map(int,input().split())
q = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  heappush(q,(s-x,1,x)) 
  heappush(q,(t-x,0,x)) 

for i in range(Q):
  d = int(input())
  heappush(q,(d,2,i))
answer = [-1]*Q

se = []
remove_task = []

while q:
  a,c,b = heappop(q)
  if not c:
    heappush(remove_task,b)
  elif c&1:
    heappush(se,b)
  else:
    while se:
      x = se[0]
      y = remove_task[0]
      if x == y:
        se.pop()
        remove_task.pop()
        continue
      else:
        answer[b] = x

print('\n'.join(map(str,answer)))


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappop
from collections import defaultdict

N,Q = map(int,readline().split())
data = list(map(int,read().split()))
S = data[:3*N:3]
T = data[1:3*N:3]
X = data[2:3*N:3]
D = data[3*N:]

event = []
event += [(s-x,1,x) for x,s in zip(X,S)] 
event += [(t-x,2,x) for x,t in zip(X,T)] 
event += [(x,3,i) for i,x in enumerate(D)] 

event.sort()

INF = 10**10
q = [INF]
counter = defaultdict(int)
counter[INF] = 1

answer = [None] * Q
for a,b,c in event:
    if b == 1:
        heappush(q,c)
        counter[c] += 1
    elif b == 2:
        counter[c] -= 1
    else:
        while counter[q[0]] == 0:
            heappop(q)
        x = q[0]
        if x == INF:
            x = -1
        answer[c] = x

print('\n'.join(map(str,answer)))

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Wrong Answer

Runtime Error

Accepted