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, bisect_right
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
def main():
    N, Q = map(int, input().split())
    kouji = [list(map(int, input().split())) for _ in range(N)]
    D = [int(input()) for _ in range(Q)]
    ans = [[-1, i+1] for i in range(Q)]
    uf = UnionFind(Q)
    kouji.sort(key=lambda x: (x[2], x[0]))
    for i in range(N):
        S, T, X = kouji[i]
        L = S-X
        R = T-X-1
        L_idx = bisect_left(D, L)
        R_idx = bisect_right(D, R)
        p = L_idx
        while p < Q and p < R_idx:
            if ans[p][0] == -1:
                ans[p][0] = X
            par = uf.parents[p]
            if par != -1:
                p = ans[par][1]
                if ans[par][1] < R_idx:
                    ans[par][1] = R_idx
                if not uf.same(L_idx, par):
                    uf.union(L_idx, par)
                    if L_idx < par:
                        if ans[L_idx][1] < ans[par][1]:
                            ans[L_idx][1] = ans[par][1]
            else:
                uf.union(L_idx, p)
                ans[p][1] = R_idx
                p += 1
    for i in range(Q):
        print(ans[i][0])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
def main():
    N, Q = map(int, input().split())
    kouji = [list(map(int, input().split())) for _ in range(N)]
    D = [int(input()) for _ in range(Q)]
    ans = [[-1, i+1] for i in range(Q)]
    uf = UnionFind(Q)
    kouji.sort(key=lambda x: (x[2], x[0]))
    for i in range(N):
        S, T, X = kouji[i]
        L = S-X
        R = T-X-1
        L_idx = bisect_left(D, L)
        R_idx = bisect_right(D, R)
        p = L_idx
        while p < Q and p < R_idx:
            if ans[p][0] == -1:
                ans[p][0] = X
            if uf.parents[p] != -1:
                pre = p
                p = ans[uf.parents[p]][1]
                if ans[pre][1] < R_idx:
                    ans[pre][1] = R_idx
                if ans[pre][1] < p:
                    ans[pre][1] = p
                if not uf.same(L_idx, pre):
                    uf.union(L_idx, pre)
                    if ans[L_idx][1] < ans[pre][1]:
                        ans[L_idx][1] = ans[pre][1]
            else:
                uf.union(L_idx, p)
                ans[p][1] = R_idx
                p += 1
    for i in range(Q):
        print(ans[i][0])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
data = []
n,q = map(int,input().split())
for i in range(n):
    s, t, x = map(int, input().split())
    data.append([s-x,t-x,x])
data.sort(key=lambda x:x[0])
d_index = 0
candidate_x = []
inf = float("inf")
data += [[inf,inf,inf]]
print(data)
for i in range(q):
    d = int(input())
    while d >= data[d_index][0]:
        heappush(candidate_x, (data[d_index][2], data[d_index][1]))
        d_index += 1
    if len(candidate_x) == 0:
        print(-1)
    else:
        while candidate_x:
            x,finish_t = heappop(candidate_x)
            if finish_t > d:
                heappush(candidate_x, (x, finish_t))
                print(x)
                break
        else:
            print(-1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
def main():
    N, Q = map(int, input().split())
    kouji = [list(map(int, input().split())) for _ in range(N)]
    D = [int(input()) for _ in range(Q)]
    ans = [[-1, i+1] for i in range(Q)]
    uf = UnionFind(Q)
    kouji.sort(key=lambda x: (x[2], x[0]))
    for i in range(N):
        S, T, X = kouji[i]
        L = S-X
        R = T-X-1
        L_idx = bisect_left(D, L)
        R_idx = bisect_right(D, R)
        p = L_idx
        while p < Q and p < R_idx:
            if ans[p][0] == -1:
                ans[p][0] = X
            if uf.parents[p] != -1:
                pre = p
                p = ans[uf.parents[p]][1]
                ans[pre][1] = R_idx
                if not uf.same(L_idx, pre):
                    uf.union(L_idx, pre)
                    if ans[L_idx][1] < R_idx:
                        ans[L_idx][1] = R_idx
                    if ans[L_idx][1] < ans[pre][1]:
                        ans[L_idx][1] = ans[pre][1]
            else:
                uf.union(L_idx, p)
                ans[p][1] = R_idx
                p += 1
    for i in range(Q):
        print(ans[i][0])

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
data = []
n,q = map(int,input().split())
for i in range(n):
    s, t, x = map(int, input().split())
    data.append([s-x,t-x,x])
data.sort(key=lambda x:x[0])
d_index = 0
candidate_x = []
inf = float("inf")
data += [[inf,inf,inf]]
for i in range(q):
    d = int(input())
    while d >= data[d_index][0]:
        heappush(candidate_x, (data[d_index][2], data[d_index][1]))
        d_index += 1
    if len(candidate_x) == 0:
        print(-1)
    else:
        while candidate_x:
            x,finish_t = heappop(candidate_x)
            if finish_t > i:
                heappush(candidate_x, (x, finish_t))
                print(x)
                break
        else:
            print(-1)

Submission status: Wrong Answer

Solution code:
N,Q=map(int,input().split())
road=[]
Ans=[]
for i in range(N):
    s,t,x=map(int,input().split())
    road.append((x,s-0.5-x,t-0.5-x))
road.sort()
for i in range(Q):
    move=0
    s=int(input())
    ans=-1
    for i in range(len(road)):
        if road[i][1]<=s<=road[i][2]:
            ans=road[i][0]
            break
        elif road[i][2]<s:
            move+=1
    for _ in range(move):
        road.pop(0)
    Ans.append(ans)
for i in range(Q):
    print(Ans[i])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

def main():
    ConstNum,PersonNum=map(int,input().split())

    S=[]
    T=[]
    X=[]
    for i in range(ConstNum):
        s,t,x=map(int,input().split())
        S.append(s)
        T.append(t)
        X.append(x)

    DepartureTime=[]
    for i in range(PersonNum):
        d=int(input())
        DepartureTime.append(d)

    STX=zip(S,T,X)
    STX=sorted(STX)
    S,T,X=zip(*STX)

    res=[-1]*PersonNum
    stop=[-1]*PersonNum

    for i in range(ConstNum):
        left_value=S[i]-X[i]
        right_value=T[i]-X[i]

        left_index=bisect_left(DepartureTime,left_value)
        right_index=bisect_left(DepartureTime,right_value)

        while left_index<right_index:
            if stop[left_index]==-1:
                res[left_index]=X[i]
                stop[left_index]=right_index
                left_index+=1
            else:
                left_index=stop[left_index]

    for i in range(PersonNum):
        print(res[i])

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

def main():
    ConstNum,PersonNum=map(int,input().split())

    S=[]
    T=[]
    X=[]
    for i in range(ConstNum):
        s,t,x=map(int,input().split())
        S.append(s)
        T.append(t)
        X.append(x)

    DepartureTime=[]
    for i in range(PersonNum):
        d=int(input())
        DepartureTime.append(d)

    STX=zip(S,T,X)
    STX=sorted(STX)
    S,T,X=zip(*STX)

    res=[-1]*PersonNum
    stop=[-1]*PersonNum

    for i in range(ConstNum):
        left_value=S[i]-X[i]
        right_value=T[i]-X[i]

        left_index=bisect_left(DepartureTime,left_value)
        right_index=bisect_left(DepartureTime,right_value)

        while left_index<right_index:
            if stop[left_index]==-1:
                res[left_index]=X[i]
                stop[left_index]=right_index
            else:
                left_index=stop[left_index]
            left_index+=1

    for i in range(PersonNum):
        print(res[i])

if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import heapq
import sys
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
q = deque()
for _ in range(p):
    q.append(int(input()))
s=set()

for t,f,x in e:
    while t > q[0]:
        q.popleft()
        if s:
            print(min(s))
        else:
            print(-1)
        if not q:
            sys.exit()
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
        
while q:
    q.pop()
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
    
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e.sort()
q = deque()
for _ in range(p):
    q.append(int(input()))
s=set()
#print(e)
for t,f,x in e:
    if t > q[0]:
        q.popleft()
        if len(s) == 0:
            print(-1)
        else:
            print(min(s))
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
while q:
    q.pop()
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
N,Q= map(int,input().split())
STX = [list(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

inf = 10**12

class SegmentTree:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.l = 2**((N-1).bit_length())
        self.data = [default]*self.l + data + [default]*(self.l-N)
        self.lazy = [default] * (self.l * 2)
        for i in range(self.l-1,0,-1):
            self.data[i] = op(self.data[2*i], self.data[2*i+1])

    def get_data(self):
        return self.data[self.l:self.l + self.N]

    def update(self,k):
        if self.lazy[k] == self.default:
            return
        if k < self.l:
            self.lazy[2*k] = self.op(self.lazy[2*k], self.lazy[k])
            self.lazy[2*k+1] = self.op(self.lazy[2*k+1], self.lazy[k])
        self.data[k] = self.op(self.data[k],self.lazy[k])
        self.lazy[k] = self.default

    def set(self,i,j,val):
        def f(self,i,j,k,s,t):
            self.update(k)
            if t <= i or j <= s: # out of range
                return
            if i <= s and t <= j: # included
                self.lazy[k] = val
                self.update(k)
                return
            f(self,i,j,2*k,s,(s+t)//2)
            f(self,i,j,2*k+1,(s+t)//2,t)
            self.data[k] = self.op(self.data[2*k], self.data[2*k+1])
        return f(self,i,j,1,0,self.l)


    def get(self,i,j):
        def g(self,i,j,k,s,t):
            self.update(k)
            if t <= i or j <= s: # out of range
                return self.default # unit element
            if i <= s and t <= j: # has intersection
                return self.data[k]
            # left + right
            return self.op(g(self,i,j,2*k,s,(s+t)//2),g(self,i,j,2*k+1,(s+t)//2,t))
        return g(self,i,j,1,0,self.l)

sstx = sum([[s-x,t-x] for s,t,x in STX],[])
sstx = sorted(set(sstx))
comp = {s:i for i,s in enumerate(sstx)}

d = np.searchsorted(sstx,D,side='left')

seg = SegmentTree([inf] * len(sstx), min, inf)
for s,t,x in STX:
    s = comp[s-x]
    t = comp[t-x]
    seg.set(s,t,x)

for di in d:
    t = seg.get(di,di+1)
    if t == inf:
        t = -1
    print(t)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, Q = map(int, input().split())
plan = []
for _ in range(N):
    s, t, x = map(int, input().split())
    start = s - x - 0.5
    end = t - x - 0.5
    plan.append((start, -1, -x))
    plan.append((end, 1, -x))
plan.sort(reverse=True)


memo = []
ans = []
for _ in range(Q):
    d = int(input())
    while plan and plan[-1][0] <= d:
        time, f, x = plan.pop()
        if f > 0:
            memo.pop()
        else:
            memo.append(-x)
    if memo:
        ans.append(memo[-1])
    else:
        ans.append(-1)

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, Q = map(int, input().split())
plan = []
for _ in range(N):
    s, t, x = map(int, input().split())
    start = s - x
    end = t - x
    plan.append((start, -1, -x))
    plan.append((end, 1, -x))
plan.sort(reverse=True)


memo = []
ans = []
for _ in range(Q):
    d = int(input())
    while plan and plan[-1][0] <= d:
        time, f, x = plan.pop()
        if f > 0:
            memo.pop()
        else:
            memo.append(-x)
    if memo:
        ans.append(memo[-1])
    else:
        ans.append(-1)

print(*ans, sep="\n")

Submission status: Wrong Answer

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

N, Q = map(int, input().split())

# 時間軸で座圧する, というかイベント管理
# order(time, flag, option)
# flag==-1: start, x
#     == 0: departure, index
#     == 1: end, x
order = []
for _ in range(N):
    #Dが[start, end]の範囲にいるとxで引っかかる
    s, t, x = map(int, input().split())
    start = s - x
    end = t - x - 1
    order.append((start, -1, x))
    order.append((end, 1, x))

for i in range(Q):
    order.append((int(input()), 0, i))
order.sort()

ans = [-1] * Q
rng = []
for _, flag, option in order:
    if flag == -1:
        rng.append(option)
    elif flag == 0:
        if rng:
            ans[option] = rng[-1]
        else:
            ans[option] = -1
    else:
        rng.pop()

print(*ans, sep="\n")

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    import bisect

    """
    各工事場所について，
    Dがどのレンジなら引っかかるかを記録しておく．
    最初全部のDに関して，infまで行けるものとして，
    Xが小さい順に工事区間を見て，引っかかるならば区間更新．
    一度値を決定した場所は飛ばしながら更新するようにすればO(Q)
    nxtを入れながら進めば各ノードを2回しか見ないからO(Q)
    事前のソートで NlogN
    """

    
    N,Q=MI()
    xst2=[]#x,ごとに，Dがどの範囲なら引っかかるか(s~t)
    xi=[[0,0]for _ in range(N)]
    for i in range(N):
        s,t,x=MI()
        xst2.append([x,s-x,t-x])
        xi[i]=[x,i]
    xi.sort()
    
    
    D=[0]*Q
    for i in range(Q):
        D[i]=I()
        
    inf=10**10
    ans=[inf]*(Q+5)#すこし多めにとっておく
    nxt=[0]*(Q+5)#次に見るべき番号
    for i in range(Q+2):
        nxt[i]=i+1
        
    
    for i in range(N):
        ii=xi[i][1]
        xx=xst2[ii][0]
        
        #1-index(手間のnxtを更新したい時があるので)
        ss=bisect.bisect_left(D,xst2[ii][1])+1
        tt=bisect.bisect_left(D,xst2[ii][2])+1
        j=ss
        nxt[ss-1]=tt
        while j<tt:
            if ans[j]==inf:
                ans[j]=xx
            j=nxt[j]
            nxt[j]=tt#次ここにきたら，ttのところまで移動するようにしておく

    
        
    for i in range(Q):
        res=ans[i+1]
        if res==inf:
            print(-1)
        else:
            print(res)
            
        
    
        

main()

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    import bisect

    """
    各工事場所について，
    Dがどのレンジなら引っかかるかを記録しておく．
    最初全部のDに関して，infまで行けるものとして，
    Xが小さい順に工事区間を見て，引っかかるならば区間更新．
    一度値を決定した場所は飛ばしながら更新するようにすればO(Q)
    nxtを入れながら進めば各ノードを2回しか見ないからO(Q)
    """

    
    N,Q=MI()
    xst2=[]#x,ごとに，Dがどの範囲なら引っかかるか(s~t)
    xi=[[0,0]for _ in range(N)]
    for i in range(N):
        s,t,x=MI()
        xst2.append([x,s-x,t-x])
        xi[i]=[x,i]
    xi.sort()
    
    
    D=[0]*Q
    for i in range(Q):
        D[i]=I()
        
    inf=10**10
    ans=[inf]*(Q+5)#すこし多めにとっておく
    nxt=[0]*(Q+5)#次に見るべき番号
    for i in range(Q+2):
        nxt[i]=i+1
        
    
    for i in range(N):
        ii=xi[i][1]
        xx=xst2[ii][0]
        
        #1index
        ss=bisect.bisect_left(D,xst2[ii][1])+1
        tt=bisect.bisect_left(D,xst2[ii][2])+1
        j=ss
        nxt[ss-1]=tt
        while j<tt:
            if ans[j]==inf:
                ans[j]=xx
            j=nxt[j]
            nxt[j]=tt+1#次ここにきたら，tt+1のところまで移動するようにしておく

    
        
    for i in range(Q):
        res=ans[i+1]
        if res==inf:
            print(-1)
        else:
            print(res)
            
        
    
        

main()

Submission status: Wrong Answer

Solution code:
import numpy as np
# 二部探索で決めていく。dpですでに見られたかどうかは把握
from bisect import bisect_left
n,q  = map(int, input().split())
imos = [0] * n
roadworks = []
for i in range(n):
    s,t,x = map(int, input().split())
    roadworks.append((s,t,x))
roadworks.sort(reverse=True)

ds = [(int(input()),i) for i in range(q)]  
ds.sort()
ix = [d[1] for d in ds]
ds = [d[0] for d in ds]
xs = np.array([-1]*(q+10))


for s,t,x in roadworks:
    l = bisect_left(ds,s-x-0.5)
    r = bisect_left(ds,t-x-0.5)    
    # print(x,l,r)
    xs[l:r] = x
    # for i in range(l,r):
    #     if xs[i] != -1:continue
    #     xs[i] = x

for i in range(q):
    print(xs[ix[i]])

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline()
from bisect import bisect_left, bisect_right

class LazySegmentTree:
    INF = float("inf")

    def __init__(self, n):
        self.n = 1 << (n-1).bit_length()
        self.data = [self.INF] * (self.n*2)
        self.lazy = [None] * (self.n*2)
    
    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.n+i] = x
        for i in range(self.n-1, 0, -1):
            self.data[i] = min(self.data[i*2], self.data[i*2+1])
        
    def query(self, l, r):
        if not l < r: return self.INF
        self.propagate(self.__getidx(l, r))

        l += self.n; r += self.n 
        res = self.INF
        while l < r:
            if l & 1:
                res = min(res, self.data[l])
                l += 1
            if r & 1:
                res = min(res, self.data[r-1])
            l >>= 1; r >>= 1
        return res
    
    def update(self, l, r, x):
        if not l < r: return
        idx = self.__getidx(l, r)
        self.propagate(idx)

        l += self.n; r += self.n 
        while l < r:
            if l & 1:
                self.data[l], self.lazy[l] = x, x
                l += 1
            if r & 1:
                self.data[r-1], self.lazy[r-1] = x, x
            l >>= 1; r >>= 1
    
        for i in idx:
            self.data[i] = min(self.data[i*2], self.data[i*2+1])

    def __getidx(self, l, r):
        l += self.n; r += self.n 
        lm = l // ((l & -l) << 1)
        rm = r // ((r & -r) << 1)
        res = []
        while l < r:
            if l <= lm: res.append(l)
            if r <= rm: res.append(r)
            l >>= 1; r >>= 1
        while l:
            res.append(l)
            l >>= 1
        return res
    
    def propagate(self, idx):
        for i in reversed(idx):
            val = self.lazy[i]
            if val is None: continue
            self.lazy[i*2] = val; self.lazy[i*2+1] = val
            self.data[i*2] = val; self.data[i*2+1] = val
            self.lazy[i] = None

n, q = map(int, input().split())
query = [None] * n
for i in range(n):
    s, t, x = map(int, input().split())
    query[i] = s-x, t-x, x
d = [int(input()) for _ in range(q)]
lst = LazySegmentTree(q)

query.sort(key=lambda x: x[2], reverse=True)

for l, r, x in query:
    lst.update(bisect_left(d, l), bisect_left(d, r), x)

lst.propagate(range(lst.n))

for i in range(q):
    ans = lst.data[i+lst.n]
    print(-1 if ans == float("inf") else ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
            self.depth=n.bit_length()
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s
        
        def lower_bound(self,x):
            sum_=0
            pos=0
            for i in range(self.depth,-1,-1):
                k=pos+(1<<i)
                if k<=self.num and sum_+self.dat[k]<x:
                    sum_+=self.dat[k]
                    pos+=1<<i
            return pos, sum_
    
    N,Q=map(int,input().split())
    S,T,X=[0]*N,[0]*N,[0]*N
    for i in range(N):
        S[i],T[i],X[i]=map(int,input().split())
    unique_X=sorted(list(set(X)))
    d={unique_X[i]:i for i,x in enumerate(unique_X)}
    h=[]
    for i in range(N):
        heappush(h,(S[i]-X[i],1,d[X[i]]))
        heappush(h,(T[i]-X[i],-1,d[X[i]]))
    for _ in range(Q):
        heappush(h,(int(input()),2,0))
    b=BIT(len(unique_X))
        


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,Q=map(int,input().split())
    S,T,X=[0]*N,[0]*N,[0]*N
    for i in range(N):
        S[i],T[i],X[i]=map(int,input().split())
    h=[]
    for i in range(N):
        heappush(h,(S[i]-X[i],1,X[i]))
        heappush(h,(T[i]-X[i],-1,X[i]))
    c=0


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,Q=map(int,input().split())
    S,T,X=[0]*N,[0]*N,[0]*N
    for i in range(N):
        S[i],T[i],X[i]=map(int,input().split())
    l=[]
    for i in range(N):
        l.append((S[i]-X[i],1,X[i]))
        l.append((T[i]-X[i],-1,X[i]))
    l.sort()
    c=0


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,Q=map(int,input().split())
    S,T,X=[0]*N,[0]*N,[0]*N
    for i in range(N):
        S[i],T[i],X[i]=map(int,input().split())
    l=[]
    for i in range(N):
        l.append((S[i]-X[i],1,X[i]))
        l.append((T[i]-X[i],-1,X[i]))
    c=0


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,Q=map(int,input().split())
    S,T,X=[0]*N,[0]*N,[0]*N
    for i in range(N):
        S[i],T[i],X[i]=map(int,input().split())
    l=[]
    for i in range(N):
        l.append((S[i]-X[i],1,X[i]))
        l.append((T[i]-X[i],-1,X[i]))
    l.sort()
    c=0


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,Q=map(int,input().split())
    S,T,X=[0]*N,[0]*N,[0]*N
    for i in range(N):
        S[i],T[i],X[i]=map(int,input().split())
    l=[]
    for i in range(N):
        l.append((S[i]-X[i],1,X[i]))
        l.append((T[i]-X[i],-1,X[i]))
    l+=[(int(input()),2,0) for _ in range(Q)]
    l.sort()
    c=0


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,Q=map(int,input().split())
    S,T,X=[0]*N,[0]*N,[0]*N
    for i in range(N):
        S[i],T[i],X[i]=map(int,input().split())
    l=[]
    for i in range(N):
        l.append((S[i]-X[i],1,X[i]))
        l.append((T[i]-X[i],-1,X[i]))
    c=0


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
            self.depth=n.bit_length()
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s
        
        def lower_bound(self,x):
            sum_=0
            pos=0
            for i in range(self.depth,-1,-1):
                k=pos+(1<<i)
                if k<=self.num and sum_+self.dat[k]<x:
                    sum_+=self.dat[k]
                    pos+=1<<i
            return pos, sum_
    
    N,Q=map(int,input().split())
    S,T,X=[0]*N,[0]*N,[0]*N
    for i in range(N):
        S[i],T[i],X[i]=map(int,input().split())
    l=[]
    for i in range(N):
        l.append((S[i]-X[i],1,X[i]))
        l.append((T[i]-X[i],-1,X[i]))
    l+=[(int(input()),2,0) for _ in range(Q)]
    l.sort()
    c=0


if __name__ == '__main__':
    main()