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):
#!/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])    


# -*- 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])    


# -*- 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])    


#!/usr/bin/python3
# -*- 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 = [int(readl().rstrip()) for _ in range(Q)] + [10**10]
  ans = [[0,0] for _ in range(Q)]
  i = 0

  STX = sorted(STX,key=lambda x:x[2])
  for s,t,x in STX:
    l = r = bisect_left(Dn,s-x)
    t -= x
    while Dn[r] < t:
      ans[i] = [Dn[r],x]
      i += 1
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    ans[i] = [d,-1]

  return sorted(ans),Q


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

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = deque()
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX.append([x,s-x,t-x])
  Dn = [int(stdin.readline().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  for x,s,t in sorted(list(STX)):
    l = bisect_left(Dn,s)
    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


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


# -*- 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])    


#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in xrange(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(stdin.readline().rstrip()) for _ in xrange(Q)] + [10**10]
  ans = []

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    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


if __name__ == "__main__":
  ans = main()
  while len(ans) > 0:
    print(heappop(ans)[1])    


# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin



readl = stdin.readline

## 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 = [-1] * (Q+1)
skip = [-1] * (Q+1)

for s,t,x in sorted(STX,key=lambda x:x[2]):
  l = bisect_left(Dn,s-x)
  r = bisect_left(Dn,t-x)
  while l < r:
    if skip[l] < 0:
      ans[l] = x
      skip[l] = r
      l += 1
    else:
      l = skip[l]

for d in ans[:-1]:
  print(d)

Verdicts: Runtime Error

Runtime Error

Runtime Error

Wrong Answer

Runtime Error

Runtime Error

Runtime Error

Accepted