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: Wrong Answer

Solution code:
from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline

INF = 10**10

N, Q = map(int, input().split())
roadworks = [tuple(map(int, input().split())) for _ in range(N)]
Ds = [int(input()) for _ in range(Q)]

events = []
for iR, (S, T, X) in enumerate(roadworks):
    events.append((S-X, 0, X, iR))
    events.append((T-X, 1, -X, iR))
events.sort()

isActives = [False] * N
anss = [-1] * Q
iD = 0
xNow, iNow = INF, -1
PQ = []
for tm, ST, x, iR in events:
    if ST == 0:  # 工事の開始
        isActives[iR] = True
        if x <= xNow:
            while iD < Q and Ds[iD] < tm:
                anss[iD] = xNow if xNow != INF else -1
                iD += 1
            xNow, iNow = x, iR
        heappush(PQ, (x, iR))
    else:  # 工事の終了
        isActives[iR] = False
        if iR == iNow:
            while iD < Q and Ds[iD] < tm:
                anss[iD] = xNow
                iD += 1
            xNow, iNow = INF, -1
            while PQ:
                x, i = heappop(PQ)
                if isActives[i]:
                    xNow, iNow = x, i
                    break

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

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush
N,Q=list(map(int,input().split()))
Event=[]
for i in range(N):
    S,T,X=(list(map(int,input().split())))
    Event.append((S-X,1,X))
    Event.append((T-X,-1,X))
Event=sorted(Event,key=lambda x:x[0])
s=[]#set()
iev=0
for i in range(Q):
    dd=int(input())
    while iev<2*N and Event[iev][0]<=dd:
        if Event[iev][1]==1:
            heappush(s,Event[iev][2])
        else:
            s.remove(Event[iev][2])
        iev+=1
    print(s[0] if s else -1)

Submission status: Wrong Answer

Solution code:
#test
N, Q = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

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

L = [[-1, -1]] * Q
for s, t, x in STX:
  n = s - x
  ok = Q
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if D[mid] >= n:
      ok = mid
    else:
      ng = mid
  l = ok

  n = t - x
  ok = Q
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if D[mid] >= n:
      ok = mid
    else:
      ng = mid
  r = ok
  continue
  while l < r:
    if L[l][1] == -1:
      L[l] = [x, r]
      l += 1
    else:
      l = L[l][1]

for i in L:
  print(i[0])

Submission status: Wrong Answer

Solution code:
#test
N, Q = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

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

L = [[-1, -1]] * Q
for s, t, x in STX:
  n = s - x
  ok = Q
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if D[mid] >= n:
      ok = mid
    else:
      ng = mid
  l = ok

  n = t - x
  ok = Q
  ng = l - 1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if D[mid] >= n:
      ok = mid
    else:
      ng = mid
  r = ok
  continue
  while l < r:
    if L[l][1] == -1:
      L[l] = [x, r]
      l += 1
    else:
      l = L[l][1]

for i in L:
  print(i[0])

Submission status: Wrong Answer

Solution code:
#test
def hersCode(L, n):
  ok = len(L)
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok

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

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

  L = [[-1, -1]] * Q
  for s, t, x in STX:
    l = hersCode(D, s - x)
    r = hersCode(D, t - x)
    continue
    while l < r:
      if L[l][1] == -1:
        L[l] = [x, r]
        l += 1
      else:
        l = L[l][1]

  for i in L:
    print(i[0])

main()

Submission status: Wrong Answer

Solution code:
def hersCode(L, n):
  ok = len(L) - 1
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok

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

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

  L = [[-1, -1]] * Q
  for s, t, x in STX:
    l = hersCode(D, s - x - 1)
    r = hersCode(D, t - x)

    while l < r:
      if L[l][1] == -1:
        L[l] = [x, r]
        l += 1
      else:
        l = L[l][1]

  for i in L:
    print(i[0])

main()

Submission status: Wrong Answer

Solution code:
def hersCode(L, n):
  ok = len(L) - 1
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok

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

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

  L = [-1] * Q
  X = [-1] * Q
  for s, t, x in STX:
    l = hersCode(D, s - x)
    r = hersCode(D, t - x)
    while l < r:
      if X[l] == -1:
        L[l] = x
        X[l] = r
        l += 1
      else:
        l = X[l]

  for i in L:
    print(i)

main()

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
# The person start in this location will be stopped.
work = []
for i in range(N):
    start, end, pos = map(int, input().split())
    work.append((start - pos - 0.5, end - pos - 0.5, pos))
work.sort(key=lambda x: x[0])
depart_time = [int(input()) for _ in range(Q)]
heap = []
end_time = {}
import heapq
i = 0
print(work)
for depart in depart_time:
    while i < len(work) and work[i][0] < depart:
        start, end, pos = work[i]
        heapq.heappush(heap, pos)
        end_time[pos] = end
        i += 1
    while heap and end_time[heap[0]] < depart:
        heapq.heappop(heap)
    if heap: print(heap[0])
    else: print(-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
import sys
s = sys.stdin.readlines()
N, Q = map(int, s[0].split())
x_dict = {}
for e in s[1:N + 1]:
    S, T, X = map(int, e.split())
    if X in x_dict:
        for i in range(S - 1, T):
            x_dict[X].add(i + 0.5)
    else:
        x_dict[X] = {S - 0.5}
        for i in range(S, T):
            x_dict[X].add(i + 0.5)
res_list = [-1] * Q
for x_place, x_time_set in sorted(x_dict.items()):
    for e in s[N + 1:]:
        D = int(e)
        inf_flg = 1
        time = D + x_place + 0.5
        if time in x_time_set:
            print(x_place)
            inf_flg = 0
            break
        if inf_flg == 1:
            print(-1)

Submission status: Wrong Answer

Solution code:
def hersCode(L, n):
  ok = len(L) - 1
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok

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

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

  L = [[-1, -1]] * Q
  for s, t, x in STX:
    l = hersCode(D, s - x)
    r = hersCode(D, t - x)

    while l < r:
      if L[l][1] == -1:
        L[l] = [x, r]
        l += 1
      else:
        l = L[l][1]

  for i in L:
    print(i[0])

main()

Submission status: Wrong Answer

Solution code:
def hersCode(L, n):
  ok = len(L) - 1
  ng = -1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if L[mid] >= n:
      ok = mid
    else:
      ng = mid
  return ok

N, Q = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

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

L = [[-1, 0]] * Q
for s, t, x in STX:
  l = hersCode(D, s - x)
  r = hersCode(D, t - x)

  i = l
  while i < r:
    if L[i][1] == 0:
      L[i] = [x, r]
      i += 1
    else:
      i = L[i][1]

for i in L:
  print(i[0])

Submission status: Wrong Answer

Solution code:
class RBT:
  B = 0
  R = 1

  class node:
    def __init__(s, x, col = 1):
      s.data = x
      s.col = col
      s.l = None
      s.r = None

  def __init__(s):
    s.root = None
    
  def insert(s, x):
    s.root, f = s.insert_sub(s.root, x)
    s.root.col = s.B

  def insert_sub(s, n, x):
    if n is None:
      return s.node(x), False
    if x < n.data:
      n.l, f = s.insert_sub(n.l, x)
      return s.check_left(n, f)
    else:
      n.r, f = s.insert_sub(n.r, x)
      return s.check_right(n, f)

  def check_left(s, n, f):
    if f:
      return n, f
    if n.col == s.B:
      f = True
      if n.l.r is not None and n.l.r.col == s.R:
        n.l = s.rot_left(n.l)
      if n.l.l is not None and n.l.l.col == s.R:
        if n.r is not None and n.r.col == s.R:
          s.split(n)
          f = False
        else:
          n = s.rot_right(n)
    return n, f

  def check_right(s, n, f):
    if f:
      return n, f
    if n.col == s.B:
      f = True
      if n.r.l is not None and n.r.l.col == s.R:
        n.r = s.rot_right(n.r)
      if n.r.r is not None and n.r.r.col == s.R:
        if n.l is not None and n.l.col == s.R:
          s.split(n)
          f = False
        else:
          n = s.rot_left(n)
    return n, f

  def rot_left(s, n):
    rn = n.r
    n.r = rn.l
    rn.l = n
    rn.col = n.col
    n.col = s.R
    return rn
  
  def rot_right(s, n):
    ln = n.l
    n.l = ln.r
    ln.r = n
    ln.col = n.col
    n.col = s.R
    return ln

  def split(s, n):
    n.col = s.R
    n.l.col = s.B
    n.r.col = s.B

  def check_col(s, n, col):
    return n is not None and n.col == col

  def keep_right(s, n, f):
    if f:
      return n, f
    if s.check_col(n.l.l, s.B) and s.check_col(n.l.r, s.B):
      if n.l.col == s.B:
        n.l.col = s.R
        if n.col == s.B:
          return n, False
        n.col = s.B
      else:
        n = s.lot_right(n)
        n.r, _ = s.keep_right(n.r, False)
    else:
      if s.check_col(n.l.r, s.R):
        n.l = s.rot_left(n.l)
      n = s.rot_right(n)
      n.r.col = s.B
      n.l.col = s.B
      return n, True

  def keep_left(s, n, f):
    if f:
      return n, f
    if s.check_col(n.r.l, s.B) and s.check_col(n.r.r, s.B):
      if n.r.col == s.B:
        n.r.col = s.R
        if n.col == s.B:
          return n, False
        n.col = s.B
      else:
        n = s.lot_left(n)
        n.l, _ = s.keep_left(n.l, False)
    else:
      if s.check_col(n.r.l, s.R):
        n.r = s.rot_right(n.r)
      n = s.rot_left(n)
      n.l.col = s.B
      n.r.col = s.B
      return n, True

  def isNone(s):
    return s.root == None

  def get_min(s):
    return s.get_min_sub(s.root)

  def get_min_sub(s, n):
    while n.l is not None:
      n = n.l
    return n.data

  def delete(s, x):
    s.root, f = s.delete_sub(s.root, x)

  def delete_sub(s, n, x):
    if n is None:
      return n, True
    if x == n.data:
      if n.l is None and n.r is None:
        return None, n.col == s.R
      elif n.r is None:
        n.l.col = s.B
        return n.l, True
      elif n.l is None:
        n.r.col = s.B
        return n.r, True
      else:
        n.data = s.get_min_sub(n.r)
        n.r, f = s.delete_sub(n.r, n.data)
        return s.keep_right(n, f)
    elif x < n.data:
      n.l, f = s.delete_sub(n.l, x)
      return s.keep_left(n, f)
    else:
      n.r, f = s.delete_sub(n.r, x)
      return s.keep_right(n, f)

  def print_node(s, n, x):
    color = ("B", "R")
    if n is not None:
      s.print_node(n.l, x + 1)
      print("   " * x, color[n.col], n.data)
      s.print_node(n.r, x + 1)

N, Q = list(map(int, input().split()))
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]

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

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

rbt = RBT()

dc = 0
lc = 0
while dc < len(D):
  if lc == len(L) or D[dc] < L[lc][0]:
    if rbt.isNone():
      t = -1
    else:
      t = rbt.get_min()
    while lc == len(L) or D[dc] < L[lc][0]:
      print(t)
      dc += 1
      if dc == len(D):
        break
  else:
    while D[dc] >= L[lc][0]:
      k = L[lc][1]
      if k < 0:
        rbt.delete(-k)
      else:
        rbt.insert(k)
      lc += 1
      if lc == len(L):
        break

Submission status: Wrong Answer

Solution code:
import bisect,heapq
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False

n,q = inm()
stx = []
for i in range(n):
    s,t,x = inm()
    stx.append((s,t,x))
d = []
for i in range(q):
    x = inn()
    d.append(x)

ls = [ [] for i in range(q) ]
rs = [ [] for i in range(q+1) ]
for i in range(n):
    s,t,x = stx[i]
    if t-x <= d[0] or d[q-1] < s-x:
        continue
    l = bisect.bisect_left(d,s-x)
    r = l + bisect.bisect_left(d[l:],t-x)
    ls[l].append(x)
    rs[r].append(x)

dist = [0] * q
hp = []
mark = {}
for i in range(q):
    for z in rs[i]:
        mark[z] = True
    for z in ls[i]:
        heapq.heappush(hp,z)
        mark[z] = False
    while len(hp)>0 and mark.get(hp[0]):
        heapq.heappop(hp)
    dist[i] = -1 if len(hp)==0 else hp[0]

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

Submission status: Wrong Answer

Solution code:
import sys,bisect,heapq
#from collections import defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,q = inm()
stx = []
for i in range(n):
    s,t,x = inm()
    stx.append((s,t,x))
d = []
for i in range(q):
    x = inn()
    d.append(x)

ls = [ [] for i in range(q) ]
rs = [ [] for i in range(q+1) ]
for i in range(n):
    s,t,x = stx[i]
    if t-x <= d[0] or d[q-1] < s-x:
        continue
    l = bisect.bisect_left(d,s-x)
    r = bisect.bisect_left(d,t-x)
    ddprint("s {} t {} x {} l {} r {}".format(s,t,x,l,r))
    ls[l].append(x)
    rs[r].append(x)

ddprint(ls)
ddprint(rs)
dist = [0] * q
hp = []
mark = {} #defaultdict(bool)
for i in range(q):
    for z in rs[i]:
        mark[z] = True
    for z in ls[i]:
        heapq.heappush(hp,z)
        mark[z] = False
    while len(hp)>0 and mark.get(hp[0]): # mark[hp[0]]:
        heapq.heappop(hp)
    dist[i] = -1 if len(hp)==0 else hp[0]
    if DBG:
        hp2 = [x for x in hp]
        tmpa = []
        while len(hp2)>0:
            tmpa.append(heapq.heappop(hp2))
        printn('hp: ')
        print(tmpa)
        printn('mark: ')
        print(mark)

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

Submission status: Wrong Answer

Solution code:
import sys,bisect,heapq
from collections import defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,q = inm()
stx = []
for i in range(n):
    s,t,x = inm()
    stx.append((s,t,x))
d = []
for i in range(q):
    x = inn()
    d.append(x)

ls = [ [] for i in range(q) ]
rs = [ [] for i in range(q+1) ]
for i in range(n):
    s,t,x = stx[i]
    if t-x <= d[0] or d[q-1] < s-x:
        continue
    l = bisect.bisect_left(d,s-x)
    r = bisect.bisect_left(d,t-x)
    #ddprint("s {} t {} x {} l {} r {}".format(s,t,x,l,r))
    ls[l].append(x)
    rs[r].append(x)

#ddprint(ls)
#ddprint(rs)
dist = [0] * q
hp = []
mark = defaultdict(bool)
for i in range(q):
    for z in rs[i]:
        mark[z] = True
    for z in ls[i]:
        heapq.heappush(hp,z)
        mark[z] = False
    while len(hp)>0 and mark[hp[0]]:
        heapq.heappop(hp)
    dist[i] = -1 if len(hp)==0 else hp[0]

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

Submission status: Wrong Answer

Solution code:
import sys,bisect,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,q = inm()
stx = []
for i in range(n):
    s,t,x = inm()
    stx.append((s,t,x))
d = []
for i in range(q):
    x = inn()
    d.append(x)

ls = [ [] for i in range(q) ]
rs = [ [] for i in range(q+1) ]
for i in range(n):
    s,t,x = stx[i]
    if t-x <= d[0] or d[q-1] < s-x:
        continue
    l = bisect.bisect_left(d,s-x)
    r = bisect.bisect_left(d,t-x)
    ddprint("s {} t {} x {} l {} r {}".format(s,t,x,l,r))
    ls[l].append(x)
    rs[r].append(x)

ddprint(ls)
ddprint(rs)
dist = [0] * q
hp = []
mark = defaultdict(bool)
for i in range(q):
    for z in rs[i]:
        mark[z] = True
    for z in ls[i]:
        heapq.heappush(hp,z)
        mark[z] = False
    while len(hp)>0 and mark[hp[0]]:
        heapq.heappop(hp)
    dist[i] = -1 if len(hp)==0 else hp[0]

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

Submission status: Wrong Answer

Solution code:
import sys, math, collections, heapq, itertools
from bisect import bisect_left
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def initialize(N):
    d, k = 1, 0
    while d < N:
        d *= 2
        k += 1
    L = [10 ** 20] * (2*d-1)
    return L, k

def change(i, j, a, left, right, level, where, btree, k):  
    if j <= left or i >= right: return
    elif i <= left and right <= j:
        if a < btree[where]:
            btree[where] = a
            while level < k:
                btree[2 * where + 1] = a
                btree[2 * where + 2] = a
                where *= 2
                level += 1
    else:
        change(i, j, a, left, (left + right)//2, level + 1, 2 * where + 1, btree, k)
        change(i, j, a, (left + right)//2, right, level + 1, 2 * where + 2, btree, k)

N, Q = map(int, line_input())
stop = [[] for i in range(N)]
for i in range(N):
    s, t, x = map(int, line_input())
    stop[i] = (x, s, t)
stop.sort(reverse = True)
D = [int(single_input()) for i in range(Q)]
cango, k = initialize(Q)
for i in range(N):
    sleft = bisect_left(D, max(stop[i][1] - stop[i][0], 0))
    sright = bisect_left(D, max(stop[i][2] - stop[i][0], 0))
    change(sleft, sright, stop[i][0], 0, 2 ** k , 0, 0, cango, k)
for i in range(Q):
    if cango[pow(2, k) - 1 + i] == 10 ** 20: print(-1)
    else: print(cango[pow(2, k) - 1 + i])

Submission status: Wrong Answer

Solution code:
import sys, math, collections, heapq, itertools
from bisect import bisect_left
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def initialize(N):
    d, k = 1, 0
    while d < N:
        d *= 2
        k += 1
    L = [10 ** 20] * (2*d-1)
    return L, k

def change(i, j, a, left, right, level, where, btree, k):  
    if j <= left or i >= right: return
    elif i <= left and right <= j:
        if a < btree[where]:
            btree[where] = a
            while level < k:
                btree[2 * where + 1] = a
                btree[2 * where + 2] = a
                where *= 2
                level += 1
    else:
        change(i, j, a, left, (left + right)//2, level + 1, 2 * where + 1, btree, k)
        change(i, j, a, (left + right)//2, right, level + 1, 2 * where + 2, btree, k)

N, Q = map(int, line_input())
stop = [[] for i in range(N)]
for i in range(N):
    s, t, x = map(int, line_input())
    stop[i] = (x, s, t)
stop.sort(reverse = True)
D = [int(single_input()) for i in range(Q)]
cango, k = initialize(Q)
for i in range(N):
    sleft = bisect_left(D, max(stop[i][1] - stop[i][0], 0))
    sright = bisect_left(D, max(stop[i][2] - stop[i][0], 0))
    change(sleft, sright, stop[i][0], 0, 2 ** k , 0, 0, cango, k)
for i in range(Q):
    if cango[pow(2, k) - 1 + i] == 10 ** 20: print(-1)
    else: print(cango[pow(2, k) - 1 + i])

Submission status: Wrong Answer

Solution code:
N , Q = map(int,input().split())

D = [0]*Q
Input = []
length = [0]*Q

for i in range(N):
    Input.append(list(map(int,input().split())))

time = lambda A : A[1]
Input.sort(key=time)


for i in range(Q):
    D[i] = int(input())

# i番目の人の座標を計算
for i in range(Q):
    length[i] = []
    # 可能性のある通行止め
    stop = 0
    for j in range(N):
        if(Input[j][0] <= D[i]):
            continue

        stopTime = Input[j][2] + D[i]

        if(stopTime >= Input[j][0] - 0.5 and stopTime <= Input[j][1] - 0.5):
            length[i].append(Input[j][2])

for l in length:
    if(len(l) == 0):
        print(-1)
    else:
        print(min(l))

Submission status: Wrong Answer

Solution code:
#D in [S_i-X_i,T_i-X_i) → Xiで止まる
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)) # xで止まらなくなる
  task.append((s-x,1,x)) # xで止まる

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_sort = [] # heapでソートを保つ

# 小さい時刻から順に見ていく
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)))

Submission status: Wrong Answer

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math
import heapq


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // (math.factorial(x - y) * math.factorial(y))

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


###############################################################################


# n : kouji count
def main():
    n, q = intin()
    stxlist = intinl(n)
    dlist = intinl(q)

    stxlist = [(s - x, t - x, x) for s, t, x in stxlist]

    event_list = []
    for s, t, x in stxlist:
        event_list.append((s, 1, x))
        event_list.append((t, -1, x))

    for d in dlist:
        event_list.append((d, 2, 0))

    event_list.sort()

    stop_list = []
    remove_dict = defaultdict(lambda: False)
    for time, event, x in event_list:
        if event == 2:
            if stop_list:
                print(stop_list[0])
            else:
                print(-1)
        if event == 1:
            heapq.heappush(stop_list, x)
        if event == -1:
            remove_dict[x] = True
            while stop_list and remove_dict[stop_list[0]]:
                remove_dict[stop_list[0]] = False
                heapq.heappop(stop_list)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math
import heapq


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // (math.factorial(x - y) * math.factorial(y))

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


###############################################################################


# n : kouji count
def main():
    n, q = intin()
    stxlist = intinl(n)
    dlist = intinl(q)

    stxlist = [(s - x, t - x, x) for s, t, x in stxlist]

    event_list = []
    for s, t, x in stxlist:
        event_list.append((s, 1, x))
        event_list.append((t, -1, x))

    for d in dlist:
        event_list.append((d, 2, 0))

    event_list.sort()

    stop_list = []
    remove_dict = defaultdict(lambda: False)
    for time, event, x in event_list:
        if event == 2:
            if stop_list:
                print(stop_list[0])
            else:
                print(-1)
        if event == 1:
            heapq.heappush(stop_list, x)
        if event == -1:
            remove_dict[x] = True
            while stop_list and remove_dict[stop_list[0]]:
                pop_x = heapq.heappop(stop_list)
                remove_dict[pop_x] = False


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left
    from array import array
    I=10**9+1
    n,*t=open(0)
    n,q=map(int,n.split())
    *d,=map(int,t[n:])
    z=[]
    for t in t[:n]:
        s,t,x=map(int,t.split())
        z.append((x,bisect_left(d,s-x),bisect_left(d,t-x)))
    N0=2**(q-1).bit_length()
    data=array('I',[I]*2*N0)
    for x,l,r in sorted(z)[::-1]:
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        s=data[k+N0-1]
        print(-(s==I)or s)
if __name__=='__main__':
    main()