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 bisect import bisect_left
n, Q = list(map(int, input().split()))
stx = [list(map(int, input().split())) for i in range(n)]
q = [int(input()) for i in range(Q)]
stx.sort(key=lambda x: x[2])
ans = [-1 for i in range(Q)]

for (s, t, x) in stx:
  begin = bisect_left(q, s-x)
  end = bisect_left(q, t-x)
  while begin<end and ans[begin]==-1:
    ans[begin] = x
    begin += 1
  while begin<end and ans[end-1]==-1:
    ans[end-1] = x
    end -= 1
for e in ans:
  print(e)

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left
    I=10**9+1
    n,q,*t=map(int,open(0).read().split())
    d=tuple(t[-q:])
    t=t[:-q]
    N0=2**(q-1).bit_length()
    data=[I]*2*N0
    for x,l,r in sorted(((x,bisect_left(d,s-x)+N0,bisect_left(d,t-x)+N0)for s,t,x in zip(t[::3],t[1::3],t[2::3])),reverse=1):
        while l<r:
            if r&1:r-=1;data[r-1]=x
            if l&1:data[l-1]=x;l+=1
            l>>=2;r>>=2
    a=[]
    for k in range(N0-1,q+N0-1):
        s=I
        while~k:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        a.append(-(s==I)or s)
    print('\n'.join(map(str,a)))
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    from bisect import bisect_left
    I=10**9+1
    n,q,*t=map(int,open(0).read().split())
    d=tuple(t[-q:])
    t=t[:-q]
    N0=2**(q-1).bit_length()
    data=[I]*2*N0
    for x,l,r in sorted(((x,bisect_left(d,s-x)+N0,bisect_left(d,t-x)+N0)for s,t,x in zip(t[::3],t[1::3],t[2::3])),reverse=1):
        l=[l]
        [l.append(i//2)for i in l if i]
        r=[r]
        [r.append(i//2)for i in r if i]
        for l,r in zip(l,r):
            if l>=r:break
            if r&1:
                r-=1
                data[r-1]=x
            if l&1:
                data[l-1]=x
                l+=1
    a=[]
    for k in range(N0-1,q+N0-1):
        s=I
        while~k:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        a.append(-(s==I)or s)
    print('\n'.join(map(str,a)))
if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

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))
for _ in range(Q):
    d = int(input())
    events.append((d, 0, -1))
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)

Submission status: Wrong Answer

Solution code:
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [list(map(int,inputs().split())) for p in [0]*N]
M = [int(inputs()) for p in [0]*Q]
V.sort(key = lambda x:(x[0]))
count = 0
for m in M:
	for n in range(N)[count:]:
		if V[n][0] - V[n][2] <=m and m <= V[n][1] - V[n][2] -1:
			print(V[n][2])
			count = n
			break
	else:
		print(-1)

Submission status: Wrong Answer

Solution code:
# [時間、変数、処理の種類]をイベントに追加。処理の種類は1：工事開始、2：工事終了、3：判定
from heapq import *

n, q = map(int, input().split())
events = []
heapify(events)
ans = [-1] * q
koji = set()
for _ in range(n):
    s, t, x = map(int, input().split())
    heappush(events, [s - x - 0.3, x, 1])
    heappush(events, [t - x - 0.7, x, 2])
for i in range(q):
    d = int(input())
    heappush(events, [d, i, 3])
for _ in range(n * 2 + q):
    j, h, s = heappop(events)
    if s == 1:
        koji.add(h)
    elif s == 2:
        koji.remove(h)
    else:
        if koji:
            ans[h] = min(koji)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, collections, heapq
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((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:
            stopped = False
            while candidate:
                x = heapq.heappop(candidate)
                if stop[x] > 0:
                    ans += str(x) + "\n"
                    break
            else: ans += "-1\n"
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
inf=10**9+1
N,Q=map(int,input().split())
kouji=[tuple(map(int,input().split())) for i in range(N)]
kouji=[(S-X,T-X-1,X) for S,T,X in kouji]
L=1
while L<Q:
    L*=2
D=[inf]*(L+1)
for i in range(Q):
    D[i]=int(input())
MAXIDX=D[Q-1]
K=2*L-1
Min=[inf]*K
def renew(b,e,x,k,l,r):
    if b>MAXIDX or e<0:
        return
    global Min
    if D[r-1]<b or D[l]>e:
        return
    elif b<=D[l] and D[r-1]<=e:
        Min[k]=min(Min[k],x)
        return
    else:
        renew(b,e,x,2*k+1,l,(l+r)//2)
        renew(b,e,x,2*k+2,(l+r)//2,r)
    return
kouji=kouji[:1+len(kouji)//20]
for b,e,x in kouji:
    renew(b,e,x,0,0,L)
def get(q):
    ans=inf
    now=q
    while True:
        if now==0:
            break
        ans=min(ans,Min[now])
        now=(now-1)//2
    if ans>10**9:
        return -1
    return ans
for q in range(Q):
    print(get(q+L-1))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
inf=10**9+1
N,Q=map(int,input().split())
kouji=[tuple(map(int,input().split())) for i in range(N)]
kouji=[(S-X,T-X-1,X) for S,T,X in kouji]
L=1
while L<Q:
    L*=2
D=[inf]*(L+1)
for i in range(Q):
    D[i]=int(input())
MAXIDX=D[Q-1]
K=2*L-1
Min=[inf]*K
def renew(b,e,x,k,l,r):
    if b>MAXIDX or e<0:
        return
    global Min
    if D[r-1]<b or D[l]>e:
        return
    elif b<=D[l] and D[r-1]<=e:
        Min[k]=min(Min[k],x)
        return
    else:
        renew(b,e,x,2*k+1,l,(l+r)//2)
        renew(b,e,x,2*k+2,(l+r)//2,r)
    return
kouji=kouji[:1+len(kouji)//10]
for b,e,x in kouji:
    renew(b,e,x,0,0,L)
def get(q):
    ans=inf
    now=q
    while True:
        if now==0:
            break
        ans=min(ans,Min[now])
        now=(now-1)//2
    if ans>10**9:
        return -1
    return ans
for q in range(Q):
    print(get(q+L-1))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
inf=10**9+1
N,Q=map(int,input().split())
kouji=[tuple(map(int,input().split())) for i in range(N)]
kouji=[(S-X,T-X-1,X) for S,T,X in kouji]
L=1
while L<Q:
    L*=2
D=[inf]*(L+1)
for i in range(Q):
    D[i]=int(input())
MAXIDX=D[Q-1]
K=2*L-1
Min=[inf]*K
def renew(b,e,x,k,l,r):
    if b>MAXIDX or e<0:
        return
    global Min
    if D[r-1]<b or D[l]>e:
        return
    elif b<=D[l] and D[r-1]<=e:
        Min[k]=min(Min[k],x)
        return
    else:
        renew(b,e,x,2*k+1,l,(l+r)//2)
        renew(b,e,x,2*k+2,(l+r)//2,r)
    return
kouji=kouji[:1+len(kouji)//4]
for b,e,x in kouji:
    renew(b,e,x,0,0,L)
def get(q):
    ans=inf
    now=q
    while True:
        if now==0:
            break
        ans=min(ans,Min[now])
        now=(now-1)//2
    if ans>10**9:
        return -1
    return ans
for q in range(Q):
    print(get(q+L-1))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
kouji=[tuple(map(int,input().split())) for i in range(N)]
kouji=[(S-X,T-X-1,X) for S,T,X in kouji]
kouji.sort(key=lambda x:x[2])
D=[int(input()) for i in range(Q)]
MAXIDX=D[-1]
L=1
while L<Q:
    L*=2
inf=10**9+1
D+=[inf]*(L-Q+1)
K=2*L-1
Min=[inf]*K
def renew(b,e,x,k,l,r):
    if b>MAXIDX or e<0:
        return
    global Min
    if b<=D[l] and D[r-1]<=e:
        if Min[k]<x:
            return
        Min[k]=x
        return
    elif D[r-1]<b or D[l]>e:
        return
    else:
        renew(b,e,x,2*k+1,l,(l+r)//2)
        renew(b,e,x,2*k+2,(l+r)//2,r)
    return
kouji=kouji[:1+len(kouji)//4]
for b,e,x in kouji:
    renew(b,e,x,0,0,L)
def get(q):
    ans=inf
    now=q
    while True:
        if now==0:
            break
        ans=min(ans,Min[now])
        now=(now-1)//2
    if ans>10**9:
        return -1
    return ans
for q in range(Q):
    print(get(q+L-1))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
kouji=[tuple(map(int,input().split())) for i in range(N)]
kouji=[(S-X,T-X-1,X) for S,T,X in kouji]
kouji.sort(key=lambda x:x[2])
D=[int(input()) for i in range(Q)]
MAXIDX=D[-1]
L=1
while L<Q:
    L*=2
inf=float('inf')
D+=[inf]*(L-Q+1)
K=2*L-1

Min=[inf]*K

def renew(b,e,x,k,l,r):
    if b>MAXIDX or e<0:
        return
    global Min
    if b<=D[l] and D[r-1]<=e:
        if Min[k]<x:
            return
        Min[k]=x
        return
    elif D[r-1]<b or D[l]>e:
        return
    else:
        renew(b,e,x,2*k+1,l,(l+r)//2)
        renew(b,e,x,2*k+2,(l+r)//2,r)
    return
for b,e,x in kouji:
    renew(b,e,x,0,0,L)
def get(q):
    global Min
    ans=10**10
    return ans
for q in range(Q):
    print(get(q+L-1))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
kouji=[tuple(map(int,input().split())) for i in range(N)]
kouji=[(S-X,T-X-1,X) for S,T,X in kouji]
kouji.sort(key=lambda x:x[2])
D=[int(input()) for i in range(Q)]
MAXIDX=D[-1]
L=1
while L<Q:
    L*=2
inf=float('inf')
D+=[inf]*(L-Q+1)
K=2*L-1

Min=[inf]*K
lazy=[False]*K

def renew(b,e,x,k,l,r):
    if b>MAXIDX or e<0:
        return
    global Min
    if lazy[k] and k<L-1:
        if Min[2*k+1]>Min[k]:
            Min[2*k+1]=Min[k]
            lazy[2*k+1]=True
        if Min[2*k+2]>Min[k]:
            Min[2*k+2]=Min[k]
            lazy[2*k+2]=True
        lazy[k]=False
    if b<=D[l] and D[r-1]<=e:
        if Min[k]<x:
            return
        Min[k]=x
        lazy[k]=True
        return
    elif D[r-1]<b or D[l]>e:
        return
    else:
        renew(b,e,x,2*k+1,l,(l+r)//2)
        renew(b,e,x,2*k+2,(l+r)//2,r)
    return
kouji=kouji[:1+len(kouji)//4]
for b,e,x in kouji:
    renew(b,e,x,0,0,L)
def get(q):
    global Min
    ans=10**10
    now=q
    while True:
        if now==0:
            break
        ans=min(ans,Min[now])
        now=(now-1)//2
    if ans>10**9:
        return -1
    return ans
for q in range(Q):
    print(get(q+L-1))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
kouji=[tuple(map(int,input().split())) for i in range(N)]
kouji=[(S-X,T-X-1,X) for S,T,X in kouji]
kouji.sort(key=lambda x:x[2])
D=[int(input()) for i in range(Q)]
MAXIDX=D[-1]
L=1
while L<Q:
    L*=2
inf=float('inf')
D+=[inf]*(L-Q+1)
K=2*L-1

Min=[inf]*K
lazy=[False]*K

def renew(b,e,x,k,l,r):
    if b>MAXIDX or e<0:
        return
    global Min
    if lazy[k] and k<L-1:
        if Min[2*k+1]>Min[k]:
            Min[2*k+1]=Min[k]
            lazy[2*k+1]=True
        if Min[2*k+2]>Min[k]:
            Min[2*k+2]=Min[k]
            lazy[2*k+2]=True
        lazy[k]=False
    if b<=D[l] and D[r-1]<=e:
        if Min[k]<x:
            return
        Min[k]=x
        lazy[k]=True
        return
    elif D[r-1]<b or D[l]>e:
        return
    else:
        renew(b,e,x,2*k+1,l,(l+r)//2)
        renew(b,e,x,2*k+2,(l+r)//2,r)
    return
kouji=kouji[:1+len(kouji)//2]
for b,e,x in kouji:
    renew(b,e,x,0,0,L)
def get(q):
    global Min
    ans=10**10
    now=q
    while True:
        if now==0:
            break
        ans=min(ans,Min[now])
        now=(now-1)//2
    if ans>10**9:
        return -1
    return ans
for q in range(Q):
    print(get(q+L-1))

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))
for i in range(Q):
    Event.append((int(input()),2))
Event.sort()
s=[]
for i,ev in enumerate(Event):
    if ev[1]==2:
        print(s[0] if s else -1)
    elif ev[1]==1:
        heappush(s,ev[2])
    else:
        s.remove(ev[2])

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))
for i in range(Q):
    Event.append((int(input()),2))
Event.sort()
s=[]#set()
dn=set()
iev=0
ss=[]
for i,ev in enumerate(Event):
    if ev[1]==2:
        print(s[0] if s else -1)
    elif ev[1]==1:
        heappush(s,ev[2])
        ss.append([i,ev[0]," ".join(map(str,s))])
    else:
        s.remove(ev[2])

Submission status: Wrong Answer

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

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

Solution code:
import heapq as hq
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)]

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

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

main()

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush

n, q = map(int, input().split())
stx = [tuple(int(x) for x in input().split()) for _ in range(n)]
d = [int(input()) for _ in range(q)]

ans = [-1] * q

#stx.sort(reverse=True, key=itemgetter(2))

e = []

for s, t, x in stx:
    e.append([s-x, 1, x])
    e.append([t-x, -1, x])

e.sort()
e.append([10 ** 9, 1, 10 ** 9])

h = []
heappush(h, 10 ** 9)
i = 0

for p in d:
    while e[i][0] <= p:
        if e[i][1] == 1:
            heappush(h, e[i][2])
        else:
            h.remove(e[i][2])
        i += 1
    ans = h[0]
    if ans == 10 ** 9:
        print(-1)
    else:
        print(ans)

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))
for i in range(Q):
    Event.append((int(input()),2))
Event.sort()
s=[]#set()
dn=set()
iev=0
for ev in Event:
    if ev[1]==2:
        print(s[0] if s else -1)
    elif ev[1]==1:
        heappush(s,ev[2])
    else:
        dn.add(ev[2]) 
    while s and s[0] in dn:
        heappop(s)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys;input=sys.stdin.readline

from bisect import*
from collections import*
n,q=map(int,input().split())
d=defaultdict(list)
p=sorted(sorted([list(map(int,input().split()))for i in range(n)],key=lambda x:x[0]),key=lambda x:x[2])
for s,t,x in p:
    if len(d[x])>0:
        if s-x==d[x][-1][1]:
            d[x][-1][1]=t-x
        else:
            d[x].append([s-x,t-x])
    else:
        d[x].append([s-x,t-x])
#print(d)
for i in range(q):
    time=int(input())
    for k,v in d.items():
        flag=0
        for i in v:
#            print(i,t)
            if bisect_left(i,time)==1:
                print(k)
                flag=1
                break
        if flag:
            break
    if not flag:
        print(-1)

Submission status: Wrong Answer

Solution code:
import sys;input=sys.stdin.readline

from bisect import*
from collections import*
n,q=map(int,input().split())
d=defaultdict(list)
p=sorted(sorted([list(map(int,input().split()))for i in range(n)],key=lambda x:x[0]),key=lambda x:x[2])
for s,t,x in p:
    if len(d[x])>0:
        if s-x==d[x][-1][1]:
            d[x][-1][1]=t-x
        else:
            d[x].append([s-x,t-x])
    else:
        d[x].append([s-x,t-x])
#print(d)
for i in range(q):
    time=int(input())
    for k,v in d.items():
        flag=0
        for i in v:
#            print(i,t)
            if bisect_right(i,time)==1:
                print(k)
                flag=1
                break
        if flag:
            break
    if not flag:
        print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
kouji=[tuple(map(int,input().split())) for i in range(N)]
kouji=[(S-X,T-X-1,X) for S,T,X in kouji]
kouji.sort(key=lambda x:x[2])
D=[int(input()) for i in range(Q)]
L=1
while L<Q:
    L*=2
inf=float('inf')
D+=[inf]*(L-Q)
K=2*L-1

idx=[0]*K
Range=[(inf,inf)]*K
Min=[inf]*K

idx[0]=(0,L-1)
Range[0]=(D[idx[0][0]],D[idx[0][1]])
for k in range(L-1):
    l,r=idx[k]
    idx[2*k+1]=(l,(l+r)//2)
    idx[2*k+2]=((l+r)//2+1,r)
    Range[2*k+1]=(D[idx[2*k+1][0]],D[idx[2*k+1][1]])
    Range[2*k+2]=(D[idx[2*k+2][0]],D[idx[2*k+2][1]])
def renew(b,e,x,k):
    global Min
    if e<Range[k][0] or b>Range[k][1]:
        return
    b=max(Range[k][0],b)
    e=min(Range[k][1],e)
    if b==Range[k][0] and e==Range[k][1]:
        Min[k]=min(Min[k],x)
        return
    if Range[2*k+2][0]>e:
        if Min[2*k+1]<=x:
            return
        renew(max(b,Range[2*k+1][0]),min(e,Range[2*k+1][1]),x,2*k+1)
    elif Range[2*k+1][1]<b:
        if Min[2*k+2]<=x:
            return
        renew(max(b,Range[2*k+2][0]),min(e,Range[2*k+2][1]),x,2*k+2)
    else:
        renew(max(b,Range[2*k+1][0]),Range[2*k+1][1],x,2*k+1)
        renew(Range[2*k+2][0],min(e,Range[2*k+2][1]),x,2*k+2)
    return
for b,e,x in kouji:
    renew(b,e,x,0)
def get(q):
    global Min
    ans=10**10
    now=q
    while True:
        if now==0:
            break
        if ans>Min[now]:
            return Min[now]
        now=(now-1)//2
    if ans>10**9:
        return -1
    return ans
for q in range(Q):
    print(get(q+L-1))

Submission status: Wrong Answer

Solution code:
from bisect import*
from collections import*
n,q=map(int,input().split())
d=defaultdict(list)
p=sorted(sorted([list(map(int,input().split()))for i in range(n)],key=lambda x:x[0]),key=lambda x:x[2])
for s,t,x in p:
    if len(d[x])>0:
        if s==d[x][-1][1]:
            d[x][-1][1]=t
        else:
            d[x].append([s,t])
    else:
        d[x].append([s,t])
#print(d)
for i in range(q):
    time=int(input())
    for k,v in d.items():
        flag=0
        t=time+k
        for i in v:
#            print(i,t)
            if bisect_right(i,t)==1:
                print(k)
                flag=1
                break
        if flag:
            break
    if not flag:
        print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

n,q = map(int,input().split())
stx = [list(map(int,input().split())) for _ in range(n)]
stx.sort(key=lambda x:x[2])

for i in range(q):
	d = int(input())
	flag = 0
	stop_j = 10**9
	for j in range(n//2):
		# print(d[i],stx[j],stop_j)
		if stx[j][0] <= d+stx[j][2] < stx[j][1]:
			stop_j = min(stx[j][2],stop_j)
			flag = 1
			break
		elif stx[-j-1][0] <= d+stx[-j-1][2] < stx[-j-1][1]:
			stop_j = min(stx[-j-1][2],stop_j)
			flag = 2
			break
	# print(d[i],stx[j],flag)
	if flag == 1:
		print(stop_j)
	elif flag == 2:
		print(stop_j)
	else:
		print(-1)

Submission status: Wrong Answer

Solution code:
import numpy as np

n_consts, n_agents = map(int, input().split())
const_plans = []
dep_times = []
results = [-1 for _ in range(n_agents)]

for _ in range(n_consts):
    const_plans.append([int(e) for e in input().split()])

const_plans = np.array(const_plans)
order_by_x = np.argsort(const_plans.T)[-1]
const_plans = const_plans[order_by_x]

for _ in range(n_agents):
    dep_times.append(int(input()))

for n_agent, dep_time in enumerate(dep_times):
    for const_plan in const_plans:
        x = const_plan[2]
        x1 = max(0, const_plan[0] - dep_time)
        x2 = max(0, const_plan[1] - dep_time)
        if x1 <= x < x2:
            results[n_agent] = x

for result in results:
    print(result)

Submission status: Wrong Answer

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

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

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

# 距離順でソート
dist = lambda A : A[2]
Input.sort(key=dist)

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

# 出発時刻でソート
time = lambda A : A[1]
D.sort(key=time)

# i番目の人の座標を計算
skip = 0
for start in D:
    for j in range(skip,N):
        if(Input[j][1] <= start[1]): # 工事終了時刻 <= 出発時刻
            skip += 1
            continue

        stopTime = Input[j][2] + start[1] # 出発時刻 + 距離/速度

        if(stopTime >= Input[j][0] - 0.5 and stopTime <= Input[j][1] - 0.5): # 工事期間内
            length[start[0]] = Input[j][2]
            break

for i in range(Q):
    print(length[i])

Submission status: Wrong Answer

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

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

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

# 距離順でソート
dist = lambda A : A[2]
Input.sort(key=dist)

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

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

# i番目の人の座標を計算
for start in D:
    for event in Input:
        if(event[1] <= start[1]): # 工事終了時刻 <= 出発時刻
            Input.remove(event)
            continue

        stopTime = event[2] + start[1] # 出発時刻 + 距離/速度

        if(stopTime >= event[0] - 0.5 and stopTime <= event[1] - 0.5): # 工事期間内
            length[start[0]] = event[2]
            break

for i in range(Q):
    print(length[i])

Submission status: Wrong Answer

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

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

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

# 距離順でソート
dist = lambda A : A[2]
Input.sort(key=dist)

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

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

# i番目の人の座標を計算
for start in D:
    for event in Input:
        if(event[1] <= start[1]): # 工事終了時刻 <= 出発時刻
            Input.pop(0)
            continue

        stopTime = event[2] + start[1] # 出発時刻 + 距離/速度

        if(stopTime >= event[0] - 0.5 and stopTime <= event[1] - 0.5): # 工事期間内
            length[start[0]] = event[2]
            break

for i in range(Q):
    print(length[i])

Submission status: Wrong Answer

Solution code:
from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

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

N0 = 2**(Q+1).bit_length()
data = [inf]*(2*N0)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
def query(k):
    k += N0-1
    s = inf
    while k >= 0:
        if data[k]:
            s = min(s, data[k])
        k = (k-1)//2
    return s


for s,t,x in STX:
    l = bisect_left(D,s-x)
    r = bisect_left(D,t-x)
    update(l,r,x)
for d in range(Q):
    ans = query(d)
    if ans == inf:
        print(-1)
    else:
        print(ans)

Submission status: Wrong Answer

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

D = [0]*Q
Input = []
length = [-1]*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):
    stop = 0
    for j in range(N):
        if(Input[j][1] <= 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] = Input[j][2]
            break

for l in length:
    print(l)

Submission status: Wrong Answer

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

D = [0]*Q
Input = []
length = [-1]*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):
    # 可能性のある通行止め
    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] = Input[j][2]
            break

for l in length:
    print(l)

Submission status: Wrong Answer

Solution code:
import bisect
import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')
MAXINT = sys.maxsize

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

ans = np.full(Q, np.inf)

for s, t, x in STX:
    # [lo, hi) に出発した人は x で止まる
    lo = bisect.bisect_left(D, s - x)
    hi = bisect.bisect_left(D, t - x)
    ans[lo:hi] = np.minimum(x, ans[lo:hi])

for a in ans:
    print(a if a < np.inf else -1)