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: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N,Q=LI()
HQ=[]
EVS=[]
for i in range(N):
    S,T,X=LI()
    EVS.append((S-0.5-X, "s", X))
    EVS.append((T-0.5-X, "e", X))
for i in range(Q):
    D=II()
    EVS.append((D, "p", D))
EVS.sort()

st=set()
PQ=[]
for time, ev, loc in EVS:
    if ev == "s":
        heapq.heappush(PQ, loc)
        st.add(loc)
    elif ev == "e":
        st.remove(loc)
    else:
        while PQ and PQ[0] not in st:
            heapq.heappop(PQ)
        if PQ:
            print(PQ[0])
        else:
            print(-1)

Submission status: Time Limit Exceeded

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()
    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: Time Limit Exceeded

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

N,Q = map(int,input().split(" "))
querys = []
START = 1
GOAL = 0
GO = 2

for _ in range(N):
    s,t,x = (map(int,input().split(" ")))
    s -=(x + 0.5)
    t -= (x + 0.5)
    querys.append( (START,s,x) )
    querys.append( (GOAL,t,x) )

for _ in range(Q):

    querys.append( (GO,int(input()),-1)  )
koji_place = []
koji_um = set([])
heapq.heapify(koji_place)
querys = sorted(querys,key = lambda x: (x[1],x[2])  )
for query in querys:
    qtype,time,place = query
    if qtype == START:
        heapq.heappush(koji_place,place)
        koji_um.add(place)
    elif qtype == GOAL:
        koji_um.remove(place)
    elif qtype == GO:
        while koji_place and koji_place[0] not in koji_um: #更新と最近の場所のチェックを同時に行う
            heapq.heappop(koji_place) #koji place のpopは最大で place分，つまり合計で10 ** 5回行われるため ここのwhile
            # はOに影響を与えない
        if not koji_place:
            print(-1)
        else:
            print(koji_place[0])

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,Q = map(int,input().split(" "))
querys = []
START = 1
GOAL = 0
GO = 2

for _ in range(N):
    s,t,x = (map(int,input().split(" ")))
    s -=(x + 0.5)
    t -= (x + 0.5)
    querys.append( (s,START,x) )
    querys.append( (t,GOAL,x) )

for _ in range(Q):

    querys.append( (int(input()),GO,-1)  )
koji_place = []
koji_um = set([])
heapq.heapify(koji_place)
querys.sort()
for query in querys:
    time,qtype,place = query
    if qtype == START:
        heapq.heappush(koji_place,place)
        koji_um.add(place)
    elif qtype == GOAL:
        koji_um.remove(place)
    else:
        while koji_place and koji_place[0] not in koji_um: #更新と最近の場所のチェックを同時に行う
            heapq.heappop(koji_place) #koji place のpopは最大で place分，つまり合計で10 ** 5回行われるため ここのwhile
            # はOに影響を与えない
        if koji_place:
            print(koji_place[0])
        else:
            print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
N,Q = map(int,input().split(" "))
querys = []
START = 1
GOAL = 0
GO = 2

for _ in range(N):
    s,t,x = list(map(int,input().split(" ")))
    s -=(x + 0.5)
    t -= (x + 0.5)
    querys.append( (START,s,x) )
    querys.append( (GOAL,t,x) )

for _ in range(Q):
    d = int(input())
    querys.append( (GO,d,-1)  )
koji_place = []
koji_um = set()
heapq.heapify(koji_place)
querys = sorted(querys,key = lambda x:x[1])
for query in querys:
    qtype,time,place = query
    if qtype == START:
        heapq.heappush(koji_place,place)
        koji_um.add(place)
    elif qtype == GOAL:
        koji_um.remove(place)
    elif qtype == GO:
        while len(koji_place) != 0  and koji_place[0] not in koji_um: #更新と最近の場所のチェックを同時に行う
            heapq.heappop(koji_place) #koji place のpopは最大で place分，つまり合計で10 ** 5回行われるため ここのwhile
            # はOに影響を与えない
        if not koji_place:
            print(-1)
        else:
            print(koji_place[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
if __name__ == '__main__':
    N,Q=list(map(int,input().split()))
    constructions=[list(map(int,input().split())) for i in range(N)]
    D=[int(input()) for i in range(Q)]
    ans={i:-1 for i in range(Q)}
    constructions.sort(key=lambda x:x[2])

    for i,p in enumerate(D):
        for construction in constructions:
            S=construction[0]
            T=construction[1]
            X=construction[2]
            if S<=X+p<T:
                ans[i]=X
                break
    for i in ans.values():
        print(i)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    N,Q=list(map(int,input().split()))
    events=[list(map(int,input().split())) for _ in range(N)]
    D=[int(input()) for i in range(Q)]
    ans=["-1"]*Q
    skip=[-1]*Q
    events.sort(key=lambda x:x[2])
    import bisect
    for S,T,X in events:
        right=bisect.bisect_left(D,T-X)
        left=bisect.bisect_left(D,S-X)
        while left<right:
            if skip[left]==-1:
                ans[left]=str(X)
                skip[left]=right
                left+=1
            else:
                left=skip[left]
    print("\n".join(ans))

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    N,Q=list(map(int,input().split()))
    events=[list(map(int,input().split())) for _ in range(N)]
    D=[int(input()) for i in range(Q)]
    ans=[-1]*Q
    skip=[-1]*Q
    events.sort(key=lambda x:x[2])
    import bisect
    for S,T,X in events:
        right=bisect.bisect_left(D,T-X)
        left=bisect.bisect_left(D,S-X)
        while left<right:
            if skip[left]==-1:
                ans[left]=X
                skip[left]=right
                left+=1
            else:
                left=skip[left]
    for i in ans:
        print(i)

Submission status: Time Limit Exceeded

Solution code:


if __name__ == '__main__':
    N,Q=list(map(int,input().split()))
    constructions=[list(map(int,input().split())) for i in range(N)]
    D=[int(input()) for i in range(Q)]
    ans={i:-1 for i in range(Q)}
    constructions.sort(key=lambda x:x[2])

    for i,p in enumerate(D):
        for construction in constructions:
            S=construction[0]
            T=construction[1]
            X=construction[2]
            if S<=X+p<T:
                ans[i]=X
                break
    for i in ans.values():
        print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left, insort_left

input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    E = []
    
    for i in range(N):
        s, t, x = map(int, input().split())
        E.extend([(s-x-0.5, 0, x), (t-x-0.5, 1, x)])
    E.sort(reverse=True)
    
    ans = [-1] * Q
    nums = []
    
    for i in range(Q):
        d = int(input())
        
        while E and d > E[-1][0]:
            t, m, x = E.pop()
            
            if not m: insort_left(nums, x)
            else: del nums[bisect_left(nums, x)]
    
        if not E: break            
        elif nums: ans[i] = nums[0]
    for a in ans: print(a)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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
        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)
        print(mini)

Submission status: Time Limit Exceeded

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, True, pos])
    events.append([end - pos, False, pos])

events.sort()

idx = 0
candidates = set()
time, is_under_construction, pos = events[idx]
for _ in range(q):
    departure = int(input())

    while time <= departure:
        if is_under_construction:
            candidates.add(pos)
        else:
            candidates.discard(pos)
        idx += 1
        if idx == 2 * n:
            time = float('INF')
            break
        time, is_under_construction, pos = events[idx]

    if not candidates:
        print(-1)
    else:
        print(min(candidates))

Submission status: Time Limit Exceeded

Solution code:
def f():
    import sys
    input = sys.stdin.readline
    n,q=[int(j) for j in input().split()]
    l=[]
    for i in range(n):
        s,t,x=[int(j) for j in input().split()]
        l.append((s-x,1,x))
        l.append((t-x,0,x))

    for i in range(q):
        d=int(input())
        l.append((d,2,i))

    l.sort()

    ans=[-1]*q
    ll=set()
    m=10**18
    p=False
    for i,j,x in l:
        if j==1:
            ll.add(x)
            if m>x:
                m=x
                p=True
        elif j==0:
            ll.remove(x)
            if x==m:
                p=False
        else:
            if not p:
                if ll:
                    p=True
                    m=min(ll)
                else:
                    m=-1
            ans[x]=m
    print('\n'.join(map(str,ans)))

f()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,q=[int(j) for j in input().split()]
l=[]
for i in range(n):
    s,t,x=[int(j) for j in input().split()]
    l.append((s-x,1,x))
    l.append((t-x,0,x))

for i in range(q):
    d=int(input())
    l.append((d,2,i))

l.sort()

ans=[-1]*q
ll=set()
m=10**18
p=False
for i,j,x in l:
    if j==1:
        ll.add(x)
        if m>x:
            m=x
            p=True
    elif j==0:
        ll.remove(x)
        if x==m:
            p=False
    else:
        if not p:
            if ll:
                p=True
                m=min(ll)
            else:
                m=-1
        ans[x]=m
print('\n'.join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
n,q=[int(j) for j in input().split()]
l=[]
for i in range(n):
    s,t,x=[int(j) for j in input().split()]
    l.append((s-x,1,x))
    l.append((t-x,0,x))

for i in range(q):
    d=int(input())
    l.append((d,2,i))

l.sort()

ans=[-1]*q
ll=set()
m=10**18
p=False
for i,j,x in l:
    if j==1:
        ll.add(x)
        if m>x:
            m=x
            p=True
    elif j==0:
        ll.remove(x)
        if x==m:
            p=False
    else:
        if not p:
            if ll:
                p=True
                m=min(ll)
            else:
                m=-1
        ans[x]=m

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

N,Q = map(int, input().split())
List = []
dic = {}
for _ in range(N):
    s, t, x = map(int, input().split())
    List.append([s-0.5-x, 1, x])
    List.append([t-0.5-x, -1, x])
    dic[x] = False

import heapq
    
List.sort()

h = []
j = 0
for _ in range(Q):
    D = int(input())
    while j < 2*N and List[j][0] < D:
        if List[j][1] == 1:
            heapq.heappush(h, List[j][2])
            dic[List[j][2]] = True
        else:
            dic[List[j][2]] = False
        j += 1
    while h:
        ans = h[0]
        if dic[ans]:
            print(ans)
            break
        else:
            heapq.heappop(h)
    if not h:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
S = sys.stdin.readlines()

N,Q = map(int, S[0].split())
List = []
dic = {}
for i in S[1:N+1]:
    s, t, x = map(int, i.split())
    List.append([s-0.5-x, 1, x])
    List.append([t-0.5-x, -1, x])
    dic[x] = False
D = []
for i in S[N+1:]:
    D.append(int(i))

import heapq
    
List.sort()

h = []
j = 0
for i in range(Q):
    while j < 2*N and List[j][0] < D[i]:
        if List[j][1] == 1:
            heapq.heappush(h, List[j][2])
            dic[List[j][2]] = True
        else:
            dic[List[j][2]] = False
        j += 1
    while h:
        ans = h[0]
        if dic[ans]:
            print(ans)
            break
        else:
            heapq.heappop(h)
    if not h:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
S = sys.stdin.readlines()

N,Q = map(int, S[0].split())
List = []
for i in S[1:N+1]:
    s, t, x = map(int, i.split())
    List.append([s-0.5-x, 1, x])
    List.append([t-0.5-x, -1, x])
D = []
for i in S[N+1:]:
    D.append(int(i))

import heapq
    
List.sort()

h_in = []
h_ex = []
ans = []
j = 0
for i in range(Q):
    while j < 2*N and List[j][0] < D[i]:
        if List[j][1] == 1:
            heapq.heappush(h_in, List[j][2])
        else:
            heapq.heappush(h_ex, List[j][2])
        j += 1
    while len(h_in) > 0 and len(h_ex) > 0 and h_in[0] == h_ex[0]:
        heapq.heappop(h_in)
        heapq.heappop(h_ex)
    if h_in:
        ans.append(h_in[0])
    else:
        ans.append(-1)
    
for i in range(Q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
s = sys.stdin.readlines()

N,Q = map(int, s[0].split())
L = []
for i in s[1:N+1]:
    t = list(map(int, i.split()))
    L.append(t)
D = []
for i in s[N+1:]:
    D.append(int(i))

import heapq

List = []
for i in range(N):
    List.append([L[i][0]-0.5-L[i][2], 1, L[i][2]])
    List.append([L[i][1]-0.5-L[i][2], -1, L[i][2]])
    
List.sort()

h_in = []
h_ex = []
ans = []
j = 0
for i in range(Q):
    while j < 2*N and List[j][0] < D[i]:
        if List[j][1] == 1:
            heapq.heappush(h_in, List[j][2])
        else:
            heapq.heappush(h_ex, List[j][2])
        j += 1
    while len(h_in) > 0 and len(h_ex) > 0 and h_in[0] == h_ex[0]:
        heapq.heappop(h_in)
        heapq.heappop(h_ex)
    if h_in:
        ans.append(h_in[0])
    else:
        ans.append(-1)
    
for i in range(Q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
L = [[int(l) for l in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]

import heapq

List = []
for i in range(N):
    List.append([L[i][0]-0.5-L[i][2], 1, L[i][2]])
    List.append([L[i][1]-0.5-L[i][2], -1, L[i][2]])
    
List.sort()

h_in = []
h_ex = []
ans = []
j = 0
for i in range(Q):
    while j < 2*N and List[j][0] < D[i]:
        if List[j][1] == 1:
            heapq.heappush(h_in, List[j][2])
        else:
            heapq.heappush(h_ex, List[j][2])
        j += 1
    while len(h_in) > 0 and len(h_ex) > 0 and h_in[0] == h_ex[0]:
        heapq.heappop(h_in)
        heapq.heappop(h_ex)
    if h_in:
        ans.append(h_in[0])
    else:
        ans.append(-1)
    
for i in range(Q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import bisect

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

ans = [-1]*Q
L.sort(key=itemgetter(2))

K = []
for i in range(N):
    l = L[i][0]-0.5-L[i][2]
    r = L[i][1]-0.5-L[i][2]
    idx_l = bisect.bisect_left(D, l)
    idx_r = bisect.bisect_right(D, r)
    for j in range(len(K)):
        if idx_r < K[j][0]:
            K.append([idx_l, idx_r])
            break
        if idx_l <= K[j][0] < idx_r <= K[j][1]:
            idx_r = K[j][0]
            K[j][0] = idx_l
            break
        if K[j][0] <= idx_l <= K[j][1] <= idx_r:
            idx_l = K[j][1]
            K[j][1] = idx_r
            break
        if j == len(K)-1 and K[j][1] < idx_l:
            K.append([idx_l, idx_r-1])
    if i == 0:
        K.append([idx_l, idx_r-1])
    K.sort()
    for j in range(idx_l, idx_r):
        if ans[j] >= 0:
            continue
        ans[j] = L[i][2]
        
for i in range(Q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import bisect
N, Q = map(int, input().split())
STX = [list(map(int, input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]
L = [STX[i][0] - STX[i][2] -0.5 for i in range(N)]
R = [STX[i][1] - STX[i][2] -0.5 for i in range(N)]
iLR = [[i, L[i], R[i]] for i in range(N)]
iLR_L = sorted(iLR, key=lambda x:x[1])
iLR_R = sorted(iLR, key=lambda x:x[2])
#print(STX)
#print(iLR_L)
for man in D:
    tmpL = [iLR_L[i][1] for i in range(N)]
    #print(tmpL)
    left = bisect.bisect_left(tmpL, man)
    tmpR = [iLR_L[i][2] for i in range(left)]
    kouho = []
    for i, right in enumerate(tmpR):
        if man < right:
            kouho.append(iLR_L[i][0])
    if not kouho:
        print(-1)
    else:
        print(min([STX[k][2] for k in kouho]))

Submission status: Time Limit Exceeded

Solution code:
def main():
    class segtree():
        def __init__(self,basesize):#self,モノイド,元の配列
            #ini：上限（下限）,base：元の配列,monoid：モノイド,tree：セグ木,depth：treeの深さ,
            #basesize：baseの要素数,treesize：treeの要素数,num：treesize-basesize
            
            # 初期値（上限とか下限）を決定
            self.ini=10**9+1
            #セグ木の要素数（num）および深さ（depth）を計算
            self.basesize=basesize
            self.num,self.depth=1,1
            while self.num<self.basesize:
                self.num*=2
                self.depth+=1
            self.num-=1
            #関数（モノイド、今回はmin）を設定
            self.monoid=min
            #セグ木を構築
            self.treesize=self.num+self.basesize
            self.tree=[self.ini]*self.treesize
    
        #半開区間[lower,upper)について更新の準備をする関数（テスト中、minやmaxのときのみ）
        def range_update_pre(self,lower,upper,new_value):
            q=[[0,1]]  #インデックス、階層
            while q:
                i,f=q.pop()
                #popしたインデックスと階層から、求める下限と上限を算出する
                #幅
                width=pow(2,self.depth-f)
                #下限と中央と上限
                kagen=(i-pow(2,f-1)+1)*width
                chuo=kagen+width//2
                jogen=kagen+width
                k=2*i+1
                if lower<=kagen and jogen<=upper:
                    self.tree[i]=self.monoid(new_value,self.tree[i])
                    continue
                if k<self.treesize:
                    if lower<=kagen and chuo<=upper:self.tree[k]=self.monoid(new_value,self.tree[k])
                    elif lower<=chuo:q.append([k,f+1])
                if k+1<self.treesize:
                    if lower<=chuo and jogen<=upper:self.tree[k+1]=self.monoid(new_value,self.tree[k+1])
                    elif chuo<=upper:q.append([k+1,f+1])

        #更新
        def range_update(self):
            for i in range(1,self.treesize):
                self.tree[i]=self.monoid(self.tree[i],self.tree[(i-1)//2])
    from sys import stdin
    input=stdin.readline
    import bisect

    n,q=map(int,input().split())
    stx=[list(map(int,input().split())) for _ in [0]*n]
    d=[int(input()) for _ in [0]*q]
    stx=[[s-x,t-x-1,x] for s,t,x in stx]
    stx=[[bisect.bisect_left(d,s),bisect.bisect_right(d,t),x] for s,t,x in stx]
    seg=segtree(q)
    for s,t,x in stx:
        if s<t:
            seg.range_update_pre(s,t,x)
    seg.range_update()
    ans=[i for i in seg.tree[seg.treesize-seg.basesize:]]
    for i in ans:
        if i==10**9+1:
            print(-1)
        else:
            print(i)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import bisect

    n,q=map(int,input().split())
    stx=[list(map(int,input().split())) for _ in [0]*n]
    d=[int(input()) for _ in [0]*q]
    stx=[[s-x,t-x-1,x] for s,t,x in stx]
    stx=[[bisect.bisect_left(d,s),bisect.bisect_right(d,t),x] for s,t,x in stx]

    #セグ木の要素数（num）および深さ（depth）を計算
    basesize=q
    num,depth=1,1
    while num<basesize:
        num*=2
        depth+=1
    num-=1
    #セグ木を構築
    treesize=num+basesize
    tree=[10**9+1]*treesize
    
    #半開区間[lower,upper)について更新の準備をする関数
    def range_update_pre(lower,upper,new_value):
        q=[[0,1]]  #インデックス、階層
        while q:
            i,f=q.pop()
            #popしたインデックスと階層から、求める下限と上限を算出する
            #幅
            width=pow(2,depth-f)
            #下限と中央と上限
            kagen=(i-pow(2,f-1)+1)*width
            chuo=kagen+width//2
            jogen=kagen+width
            k=2*i+1
            if lower<=kagen and jogen<=upper:
                tree[i]=min(new_value,tree[i])
                continue
            if k<treesize:
                if lower<=kagen and chuo<=upper:tree[k]=min(new_value,tree[k])
                elif lower<=chuo:q.append([k,f+1])
            if k+1<treesize:
                if lower<=chuo and jogen<=upper:tree[k+1]=min(new_value,tree[k+1])
                elif chuo<=upper:q.append([k+1,f+1])

    for s,t,x in stx:
        if s<t:
            range_update_pre(s,t,x)

    for i in range(1,treesize):
        tree[i]=min(tree[i],tree[(i-1)//2])

    ans=[i for i in tree[treesize-basesize:]]
    for i in ans:
        if i==10**9+1:
            print(-1)
        else:
            print(i)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    class segtree():
        def __init__(self,basesize):#self,モノイド,元の配列
            #ini：上限（下限）,base：元の配列,monoid：モノイド,tree：セグ木,depth：treeの深さ,
            #basesize：baseの要素数,treesize：treeの要素数,num：treesize-basesize
            
            # 初期値（上限とか下限）を決定
            self.ini=10**9+1
            #セグ木の要素数（num）および深さ（depth）を計算
            self.basesize=basesize
            self.num,self.depth=1,1
            while self.num<self.basesize:
                self.num*=2
                self.depth+=1
            self.num-=1
            #関数（モノイド、今回はmin）を設定
            self.monoid=min
            #セグ木を構築
            self.treesize=self.num+self.basesize
            self.tree=[self.ini]*self.treesize
    
        #半開区間[lower,upper)について更新の準備をする関数（テスト中、minやmaxのときのみ）
        def range_update_pre(self,lower,upper,new_value):
            q=[[0,1]]  #インデックス、階層
            while q:
                i,f=q.pop()
                #popしたインデックスと階層から、求める下限と上限を算出する
                #幅
                width=pow(2,self.depth-f)
                #下限と中央と上限
                kagen=(i-pow(2,f-1)+1)*width
                chuo=kagen+width//2
                jogen=kagen+width
                k=2*i+1
                if lower<=kagen and jogen<=upper:
                    self.tree[i]=self.monoid(new_value,self.tree[i])
                    continue
                if k<self.treesize:
                    if lower<=kagen and chuo<=upper:self.tree[k]=self.monoid(new_value,self.tree[k])
                    elif lower<=chuo:q.append([k,f+1])
                if k+1<self.treesize:
                    if lower<=chuo and jogen<=upper:self.tree[k+1]=self.monoid(new_value,self.tree[k+1])
                    elif chuo<=upper:q.append([k+1,f+1])

        #更新
        def range_update(self):
            for i in range(1,self.treesize):
                self.tree[i]=self.monoid(self.tree[i],self.tree[(i-1)//2])

    import bisect

    n,q=map(int,input().split())
    stx=[list(map(int,input().split())) for _ in [0]*n]
    d=[int(input()) for _ in [0]*q]
    stx=[[s-x,t-x-1,x] for s,t,x in stx]
    stx=[[bisect.bisect_left(d,s),bisect.bisect_right(d,t),x] for s,t,x in stx]
    seg=segtree(q)
    for s,t,x in stx:
        if s<t:
            seg.range_update_pre(s,t,x)
    seg.range_update()
    ans=[i for i in seg.tree[seg.treesize-seg.basesize:]]
    for i in ans:
        if i==10**9+1:
            print(-1)
        else:
            print(i)
main()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc128/submissions/8312583
# 写経

def solve():
    from heapq import heappush, heappop
    from collections import defaultdict
    from operator import itemgetter
    import sys

    input = sys.stdin.readline

    inf = 1 << 31

    n, q = map(int, input().split())

    e = []  # 通行止めと解除にクエリ分割
    for _ in range(n):
        s, t, x = map(int, input().split())
        # 区間[s, t)に通行止め
        e.append((t - x, 0, x))  # 通行止め解除/0にすることで、解除と開始が同時刻の場合、先に解除される
        e.append((s - x, 1, x))  # 通行止め開始/1にすることで、同上

    for i in range(q):
        d = int(input())
        e.append((d, 2, i))  # 求値クエリ/2にすることで、通行止めの設定解除の反映後に到着する

    e.sort(key=itemgetter(0, 1))

    cnt = defaultdict(int)
    cnt[inf] = 1
    h = [inf]

    ret = [-1] * q
    for time, type, x in e:
        if type == 0:
            cnt[x] -= 1
        elif type == 1:
            heappush(h, x)
            cnt[x] += 1
        else:
            while not (cnt[h[0]]):
                heappop(h)
            curr = h[0]
            if curr != inf:
                ret[x] = curr

    print(*ret, sep='\n')


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    from collections import defaultdict
    from operator import itemgetter
    import sys

    input = sys.stdin.readline

    inf = 1 << 31

    n, q = map(int, input().split())

    e = []  # 通行止めと解除にクエリ分割
    for _ in range(n):
        s, t, x = map(int, input().split())
        # 区間[s, t)に通行止め
        e.append((t - x, 0, x))  # 通行止め解除/0にすることで、解除と開始が同時刻の場合、先に解除される
        e.append((s - x, 1, x))  # 通行止め開始/1にすることで、同上

    for _ in range(q):
        d = int(input())
        e.append((d, 2, -1))  # 求値クエリ/2にすることで、通行止めの設定解除の反映後に到着する

    e.sort(key=itemgetter(0, 1))

    stop_cnt = defaultdict(int)
    stop_cnt[inf] = 1
    stop_set = {inf}
    curr = inf

    ret = []
    for time, type, x in e:
        if type == 0:
            stop_cnt[x] -= 1
            if not stop_cnt[x]:
                stop_set.discard(x)
                if curr == x:
                    curr = min(stop_set)
        elif type == 1:
            stop_cnt[x] += 1
            if stop_cnt[x] == 1:
                stop_set.add(x)
            if x < curr:
                curr = x
        else:
            if curr == inf:
                ret.append(-1)
            else:
                ret.append(curr)

    print(*ret, sep='\n')


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    from collections import defaultdict, namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Event = namedtuple('Event', 'time type x_coordinate')

    inf = 1 << 31

    n, q = map(int, input().split())

    e = []  # 通行止めと解除にクエリ分割
    for _ in range(n):
        s, t, x = map(int, input().split())
        # 区間[s, t)に通行止め
        e.append(Event(t - x, 0, x))  # 通行止め解除/0にすることで、解除と開始が同時刻の場合、先に解除される
        e.append(Event(s - x, 1, x))  # 通行止め開始/1にすることで、同上

    for _ in range(q):
        d = int(input())
        e.append(Event(d, 2, -1))  # 求値クエリ/2にすることで、通行止めの設定解除の反映後に到着する

    e.sort(key=attrgetter('time', 'type'))

    stop_cnt = defaultdict(int)
    stop_cnt[inf] = 1
    stop_set = {inf}
    curr = inf

    for evt in e:
        if evt.type == 0:
            stop_cnt[evt.x_coordinate] -= 1
            if not stop_cnt[evt.x_coordinate]:
                stop_set.discard(evt.x_coordinate)
                if curr == evt.x_coordinate:
                    curr = min(stop_set)
        elif evt.type == 1:
            stop_cnt[evt.x_coordinate] += 1
            if stop_cnt[evt.x_coordinate] == 1:
                stop_set.add(evt.x_coordinate)
            if evt.x_coordinate < curr:
                curr = evt.x_coordinate
        else:
            if curr == inf:
                print(-1)
            else:
                print(curr)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
import heapq
n,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
L1=[]
for i in range(n):
  L1.append((l[i][0]-l[i][2],1,l[i][2]))
  L1.append((l[i][1]-l[i][2],-1,l[i][2]))
for i in range(q):
  L1.append((int(input()),2,0))
L1.sort()
L2=[]
heapq.heapify(L2)
L3=[]
L3=set(L3)
for i in range(len(L1)):
  if L1[i][1]==1:
    heapq.heappush(L2,L1[i][2])
    L3.add(L1[i][2])
  elif L1[i][1]==-1:
    L3.remove(L1[i][2])
  else:
    while L2 and L2[0] not in L3:
      heapq.heappop(L2)
    if L2:
      print(L2[0])
    else:
      print(-1)