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:
class SegmentTreeLazy():
    def __init__(self,arr,ti,ei,func,op,merge):
        self.h = len(arr).bit_length()
        self.n = 2**self.h
        self.func = func
        self.op = op
        self.merge = merge
        self.ti = ti
        self.ei = ei
        self.data = [ti for _ in range(2*self.n)]
        for i in range(len(arr)):
            self.data[i+self.n] = arr[i]
        for i in range(1,self.n)[::-1]:
            self.data[i] = self.func(self.data[2*i],self.data[2*i+1])
        self.lazy = [ei for _ in range(2*self.n)]

    def reflect(self,k):
        if self.lazy[k] == self.ei:
            return self.data[k]
        return self.op(self.data[k],self.lazy[k])

    def propagate(self,k):
        if self.lazy[k] == self.ei:
            return
        self.lazy[2*k] = self.merge(self.lazy[2*k],self.lazy[k])
        self.lazy[2*k+1] = self.merge(self.lazy[2*k+1],self.lazy[k])
        self.data[k] = self.reflect(k)
        self.lazy[k] = self.ei

    def thrust(self,k):
        for i in range(1,self.h+1)[::-1]:
            self.propagate(k >> i)

    def recalc(self,k):
        while k:
            k //= 2
            self.data[k] = self.func(self.reflect(2*k),self.reflect(2*k+1))

    def update(self,left,right,x):
        l,r = left,right
        left += self.n
        right += self.n
        self.thrust(left)
        self.thrust(right-1)
        while right-left > 0:
            if left & 1:
                self.lazy[left] = self.merge(self.lazy[left],x)
                left += 1
            if right & 1:
                right -= 1
                self.lazy[right] = self.merge(self.lazy[right],x)
            left //= 2
            right //= 2
        self.recalc(l+self.n)
        self.recalc(r+self.n-1)

    def query(self,left,right):
        left += self.n
        right += self.n
        self.thrust(left)
        self.thrust(right-1)
        tmp_l = tmp_r = self.ti
        while right-left > 0:
            if left & 1:
                tmp_l = self.func(tmp_l,self.reflect(left))
                left += 1
            if right & 1:
                right -= 1
                tmp_r = self.func(self.reflect(right),tmp_r)
            left //= 2
            right //= 2
        return self.func(tmp_l,tmp_r)



from bisect import bisect_left,bisect_right
import sys
input = sys.stdin.readline
INF = 10**18

N,Q = map(int,input().split())
P = [-INF,INF]
R = []

for i in range(N):
    s,t,x = map(int,input().split())
    R.append((s-x,t-x,x))
    P.append(s-x)
    P.append(t-x)

R = sorted(R,key=lambda x:x[2],reverse=True)
P = sorted(set(P))
S = dict()
for i in range(len(P)):
    S[P[i]] = i

st = SegmentTreeLazy(
                    arr = [-1 for _ in range(len(P))],
                    ti = 0,
                    ei = -1,
                    func = max,
                    op = lambda x,y:y if y != -1 else x,
                    merge = lambda x,y:y if y != -1 else x,
                    )
for i in range(N):
    st.update(S[R[i][0]]+1,S[R[i][1]]+1,R[i][2])

ans = []

for _ in range(Q):
    d = int(input())
    idx = bisect_left(P,d)
    ans.append(st.query(idx,idx+1))

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

Submission status: Wrong Answer

Solution code:
class SegmentTreeDual():
    def __init__(self,arr,op=lambda x,y:y if y != -1 else x,ie=-1):
        self.h = (len(arr)-1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.op = op
        self.val = [ie for _ in range(self.n)]
        self.laz = [ie for _ in range(2*self.n)]
        for i in range(len(arr)):
            self.val[i] = arr[i]
    def propagate(self,k):
        if self.laz[k] == self.ie: return
        if self.n <= k:
            self.val[k-self.n] = self.op(self.val[k-self.n],self.laz[k])
            self.laz[k] = self.ie
        else:
            self.laz[2*k] = self.op(self.laz[2*k],self.laz[k])
            self.laz[2*k+1] = self.op(self.laz[2*k+1],self.laz[k])
            self.laz[k] = self.ie
    def update(self,left,right,x):
        left += self.n
        right += self.n
        for i in range(self.h)[::-1]:
            self.propagate(left>>i)
            self.propagate(right>>i)
        while right-left>0:
            if right & 1:
                right -= 1
                self.laz[right] = self.op(self.laz[right],x)
            if left & 1:
                self.laz[left] = self.op(self.laz[left],x)
                left += 1
            left >>= 1
            right >>= 1
    def get(self,index):
        res = self.val[index]
        index += self.n
        while index>0:
            res = self.op(res,self.laz[index])
            index //= 2
        return res

from bisect import bisect_left
import sys
input = sys.stdin.readline
INF = 10**18

N,Q = map(int,input().split())
P = [-INF,INF]
R = []

for i in range(N):
    s,t,x = map(int,input().split())
    R.append((s-x,t-x,x))
    P.append(s-x)
    P.append(t-x)

R = sorted(R,key=lambda x:x[2],reverse=True)
P = sorted(set(P))
S = dict()
for i in range(len(P)):
    S[P[i]] = i

st = SegmentTreeDual([-1 for _ in range(len(P))])
for i in range(N):
    st.update(S[R[i][0]],S[R[i][1]],R[i][2])

for _ in range(Q):
    d = int(input())
    idx = bisect_left(P,d)
    print(st.get(idx))

Submission status: Wrong Answer

Solution code:
import heapq
def main():
    N, Q = map(int, input().split())
    ls = []
    lt = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        ls.append((s-x, x))
        lt.append((t-x, x))
    heapq.heapify(ls)
    heapq.heapify(lt)
    dl = set()
    for i in range(Q):
        d = int(input())
        while len(ls) > 0 and ls[0][0] <= d:
            s, x = heapq.heappop(ls)
            dl.add(x)
        dt = set()
        while len(lt) > 0 and lt[0][0] < d:
            t, x = heapq.heappop(lt)
            dt.add(x)
        dl = dl - dt
        if not dl:
            print('-1')
        else:
            print(min(dl))
main()

Submission status: Wrong Answer

Solution code:
import heapq
def main():
    N, Q = map(int, input().split())
    ls = []
    lt = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        ls.append((s-x, x))
        lt.append((t-x, x))
    heapq.heapify(ls)
    heapq.heapify(lt)
    dl = set()
    for i in range(Q):
        d = int(input())
        while len(ls) > 0 and ls[0][0] <= d:
            s, x = heapq.heappop(ls)
            dl.add(x)
        dt = set()
        while len(lt) > 0 and lt[0][0] <= d:
            t, x = heapq.heappop(lt)
            dt.add(x)
        dl = dl - dt
        if not dl:
            print('-1')
        else:
            print(min(dl))
main()

Submission status: Wrong Answer

Solution code:
import heapq

def main():
    N, Q = map(int, input().split())
    STX = [tuple(map(int, input().split())) for _ in range(N)]
    ev = []
    for s, t, x in STX:
        ev.append((s - x, True, x))
        ev.append((t - x, False, x))
    ev.sort(reverse=True)
    bar = []
    dead = {}

    for d in [int(input()) for _ in range(Q)]:
        while ev and ev[-1][0] <= d:
            t, a, x = ev.pop()
            if a:
                heapq.heappush(bar, x)
            else:
                dead[x] = dead.get(x, 0) + 1
                while bar and bar[0] in dead:
                    x = heapq.heappop(bar)
                    if dead[x] == 0:
                        del dead[x]
                    else:
                        dead[x] = dead[x] - 1
        print(bar[0] if bar else -1)

main()

Submission status: Wrong Answer

Solution code:
import heapq

def main():
    N, Q = map(int, input().split())
    STX = [tuple(map(int, input().split())) for _ in range(N)]
    ev = []
    for s, t, x in STX:
        ev.append((s - x, True, x))
        ev.append((t - x, False, x))
    ev.sort(reverse=True)
    bar = []
    dead = set()

    for d in [int(input()) for _ in range(Q)]:
        while ev and ev[-1][0] <= d:
            t, a, x = ev.pop()
            if a:
                heapq.heappush(bar, x)
            else:
                dead.add(x)
                while bar and bar[0] in dead:
                    dead.remove(heapq.heappop(bar))
        print(bar[0] if bar else -1)

main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque
N, Q = map(int, input().split())
ls = []
for i in range(N):
  s, t, x = map(int, input().split())
  heappush(ls,(s-x,0,x))
  heappush(ls,(t-x,1,x))
log = deque([float('inf')])
cnt = 0
m = float('inf')
for i in range(Q):
  d = int(input())
  while ls:
    v, f, x = heappop(ls)
    if v>d:
      break
    if f==0:
      m = min(m,x)
      log.append(m)
    else:
      if m==x:
        log.pop()
        m = log[-1]
        while cnt:
          log.pop()
          m = log[-1]
          cnt -= 1
      else:
        cnt += 1
  if m!=float('inf'):
    print(m)
  else:
    print(-1)
  heappush(ls,(v,f,x))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    # print("#F")
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    # print(S,number)
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      print(-1)
    else:
      print(heapq.heappop(hq))

Submission status: Wrong Answer

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

ev_list = []


for si, ti, xi in stx:
  ev_list.append((si-xi, 1, xi))
  ev_list.append((ti-xi, -1, xi))

ev_list.sort()

hoge = set()
i = 0

for t, b, x in ev_list:
  if i < q and d[i] < t:
    print(min(hoge) if hoge else -1)
    i += 1

  if b == 1:
    hoge.add(x)
  elif b == -1:
    hoge.remove(x)

for j in range(i, q):
  print(-1)

Submission status: Wrong Answer

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

road = []
x_list = []

for i in range(N):
    s,t,x = list(map(int,input().split()))
    road.append([0,s-x,x])
    road.append([1,t-x,x])

for i in range(Q):
    road.append([2,int(input()),i])
"""
from collections import defaultdict

counter = defaultdict(int)
counter[10**27] = 1
ans = [0]*Q

road.sort(key=lambda x:x[0])
road.sort(key=lambda x:x[1])

q = [10**27]

from heapq import heappop,heappush

for id,_,x in road:
    if id==0:
        heappush(q,x)
        counter[x]+=1
    elif id==1:
        counter[x]-=1
    else:
        while counter[q[0]]==0:
            heappop(q)
        #print(q)
        if q[0]<10**27:
            ans[x] = q[0]
        else:
            ans[x] = -1
print("\n".join(map(str,ans)))
"""

Submission status: Wrong Answer

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

road = []
x_list = []

for i in range(N):
    s,t,x = list(map(int,input().split()))
    road.append([0,s-x,x])
    road.append([1,t-x,x])

for i in range(Q):
    road.append([2,int(input()),i])

from collections import defaultdict

counter = defaultdict(int)
counter[10**27] = 1
ans = [0]*Q

road.sort(key=lambda x:x[0])
road.sort(key=lambda x:x[1])

q = [10**27]
"""
from heapq import heappop,heappush

for id,_,x in road:
    if id==0:
        heappush(q,x)
        counter[x]+=1
    elif id==1:
        counter[x]-=1
    else:
        while counter[q[0]]==0:
            heappop(q)
        #print(q)
        if q[0]<10**27:
            ans[x] = q[0]
        else:
            ans[x] = -1
print("\n".join(map(str,ans)))
"""

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import heapq
import time
import sys
input = sys.stdin.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 
 
#main
N,Q=map(int,input().split())
E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append([s-x-0.5,1,x])
    E.append([t-x-0.5,-1,x])

for a in range(Q):
    E.append([int(input()),0,0])
E.sort(key=lambda x:x[0])
 
S=set()
H=[]
for time_,type_,x in E:
    if type_==1:
        if(x in S):print(7329847)
        S.add(x)
        heapq.heappush(H,x)
    elif type_==-1:
        if(x in S):S.remove(x)
    else:
        while H and H[0] not in S:
            heapq.heappop(H)
        print(H[0] if H else -1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import heapq
import time
import sys
input = sys.stdin.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 
 
#main
N,Q=map(int,input().split())
E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append([s-x-0.5,1,x])
    E.append([t-x-0.5,-1,x])

for a in range(Q):
    E.append([int(input()),0,0])
E.sort(key=lambda x:x[0])
 
S=set()
H=[]
for time_,type_,x in E:
    if type_==1:
        S.add(x)
        heapq.heappush(H,x)
    elif type_==-1:
        if(x in S):S.remove(x)
        else: print(4723894782348279)
    else:
        while H and H[0] not in S:
            heapq.heappop(H)
        print(H[0] if H else -1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import heapq
import time
import sys
input = sys.stdin.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 
 
#main
N,Q=map(int,input().split())
E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append([s-x-0.5,1,x])
    E.append([t-x-0.5,-1,x])

for a in range(Q):
    E.append([int(input()),0,0])
E.sort(key=lambda x:x[0])
 
S=set()
H=[]
for time_,type_,x in E:
    if type_==1:
        S.add(x)
    elif type_==-1:
        a=2
        #S.remove(x)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import heapq
import time
import sys
input = sys.stdin.readline
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
 
 
#main
N,Q=map(int,input().split())
E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append([s-x-0.5,1,x])
    E.append([t-x-0.5,-1,x])

for a in range(Q):
    E.append([int(input()),0,0])
E.sort(key=lambda x:x[0])
 
S=set()
H=[]

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import heapq
import time
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n

    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]

    def same(self,x,y):
        return self.find(x)==self.find(y)

    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1

    def unite(self,x,y):
        self.link(self.find(x),self.find(y))

    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num


#main
def solve():
    return

#入力
N,Q=map(int,input().split())

E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append([s-x-0.5,1,x])
    E.append([t-x-0.5,-1,x])

for a in range(Q):
    E.append([int(input()),0,0])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import heapq
import time
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n

    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]

    def same(self,x,y):
        return self.find(x)==self.find(y)

    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1

    def unite(self,x,y):
        self.link(self.find(x),self.find(y))

    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num


#main
def solve():
    return

#入力
N,Q=map(int,input().split())

E=[]
for a in range(N):
    s,t,x=map(int,input().split())
    E.append([s-x-0.5,1,x])
    E.append([t-x-0.5,-1,x])

for a in range(Q):
    E.append([int(input()),0,0])
E.sort(key=lambda x:x[0])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 
def update(k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x,True,x,i), (t-x,False,x,i)]
    qs = []
    for _ in range(Q):
        qs.append(int(input()))
    xs.sort(key=lambda x:x[0])
    j = 0
    for x in xs:
        if qs[j] < x[0]:
            print(segl[0] if segl[0]!= mx else -1)
            j += 1
        update(x[3], x[2] if x[1] else mx)
    while Q-j:
        print(-1)
        j+=1

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 
def update(k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x,True,x,i), (t-x,False,x,i)]
    qs = []
    for _ in range(Q):
        qs.append(int(input()))
    xs.sort()
    j = 0
    for x in xs:
        if qs[j] < x[0]:
            print(segl[0] if segl[0]!= mx else -1)
            j += 1
        update(x[3], x[2] if x[1] else mx)
    while Q-j:
        print(-1)
        j+=1

Submission status: Wrong Answer

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

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update(k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[1])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)

Submission status: Wrong Answer

Solution code:


if __name__ == '__main__':
    N,Q=list(map(int,input().split()))
    events=[]
    for i in range(N):
        S,T,X=list(map(int,input().split()))
        events.append((S-X,1,X))
        events.append((T-X,-1,X))
    events.sort(key=lambda x:x[0])
    D=[int(input()) for i in range(Q)]
    ans={i:-1 for i in range(Q)}
    import copy

    for i,t in enumerate(D):
        copied=copy.deepcopy(events)
        for event in events:
            if event[0]<=t:
                copied.remove(event)
                continue
            else:
                x=min(copied,key=lambda x:x[2])
                if x[1]==-1:
                    ans[i]=x[2]
                break

    for i in ans.values():
        print(i)

Submission status: Wrong Answer

Solution code:
import numpy as np
import bisect
import sys
input = sys.stdin.readline


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

departures = [int(input()) for _ in range(q)]


ans = np.array(['-1'] * q)

for start, end, pos in events:
    left = bisect.bisect_left(departures, start-pos)
    right = bisect.bisect_left(departures, end-pos)

    ans[left: right][ans[left: right] == '-1'] = str(pos)

print('\n'.join(ans))

Submission status: Wrong Answer

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


n, q = map(int, input().split())
events = []
for _ in range(n):
    start, end, pos = map(int, input().split())
    events.append([start - pos, 1, pos])
    events.append([end - pos, 0, pos])

events.sort()

departures = [int(input()) for _ in range(q)]

idx = 0
mini = 10**10
mini_check = False
candidates = set()
time, is_under_construction, pos = events[idx]
for departure in departures:
    while time <= departure:
        if is_under_construction:
            candidates.add(pos)
            if not mini_check or pos < mini:
                mini = pos
                mini_check = True
        else:
            candidates.remove(pos)
            if pos == mini:
                mini_check = False
        idx += 1
        if idx == 2 * n:
            time = float('INF')
            break
        time, is_under_construction, pos = events[idx]

    if not candidates:
        print(-1)
    else:
        if not mini_check:
            mini = min(candidates)
            mini_check = True
        print(mini)