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:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap




@mt
def slv(N, Q, STX, D):
    from heapq import heappop, heappush
    st = [[s-x, t-x, x] for s, t, x in STX]
    st.sort(reverse=True)
    q = []
    ans = []
    for d in D:
        while st and st[-1][0] <= d:
            _, r, x = st.pop()
            heappush(q, (r, x))
        while q and q[0][0] <= d:
            heappop(q)
        if q:
            ans.append(min(a[1] for a in q))
        else:
            ans.append(-1)
    return ans






def main():
    N, Q = read_int_n()
    STX = [read_int_n() for _ in range(N)]
    D = [read_int() for _ in range(Q)]
    print(*slv(N, Q, STX, D), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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
# a_iの現在の値を取得
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
# これを呼び出す
def query(k):
    return _query(k)[1]

from bisect import bisect_left

if __name__ == '__main__':
    n, q = map(int, input().split())
    stx = [list(map(int, input().split())) for _ in range(n)]
    l = [int(input()) for _ in range(q)]

    INF = (-1, 2**31-1)
    N = len(l)
    N0 = 2**(N-1).bit_length()
    data = [None]*(2*N0)

    stx.sort(key=lambda x:x[2], reverse=True)
    for i, (s, t, x) in enumerate(stx):
        i1 = bisect_left(l, s - 0.5 - x)
        i2 = bisect_left(l, t - 0.5 - x)
        update(i1, i2, (i, x))

    for i in range(q):
        tmp = query(i)
        if tmp == INF[1]:
            print(-1)
        else:
            print(tmp)

Submission status: Time Limit Exceeded

Solution code:
# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

# 区間[l, r)をxで更新
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s


from bisect import bisect_left
from sys import stdin

if __name__ == '__main__':
    n, q = map(int, input().split())
    stx = [list(map(int, input().split())) for _ in range(n)]
    l = [int(input()) for _ in range(q)]

    INF = 2**31-1
    N = len(l)
    LV = (N-1).bit_length()
    N0 = 2**LV
    data = [INF]*(2*N0)
    lazy = [None]*(2*N0)

    stx.sort(key=lambda x:x[2], reverse=True)
    for s, t, x in stx:
        i1 = bisect_left(l, s - 0.5 - x)
        i2 = bisect_left(l, t - 0.5 - x)
        update(i1, i2, x)

    for i in range(q):
        tmp = query(i, i+1)
        if tmp == INF:
            print(-1)
        else:
            print(tmp)

Submission status: Time Limit Exceeded

Solution code:


# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

# 区間[l, r)をxで更新
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = float('inf')
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

from bisect import bisect_left
from sys import stdin

if __name__ == '__main__':
    n, q = map(int, stdin.readline().rstrip().split())
    stx = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n)]
    l = [int(stdin.readline().rstrip()) for _ in range(q)]

    N = len(l)
    LV = (N-1).bit_length()
    N0 = 2**LV
    data = [float('inf')]*(2*N0)
    lazy = [None]*(2*N0)

    stx.sort(key=lambda x:x[2], reverse=True)
    for s, t, x in stx:
        i1 = bisect_left(l, s - 0.5 - x)
        i2 = bisect_left(l, t - 0.5 - x)
        update(i1, i2, x)

    for i in range(q):
        tmp = query(i, i+1)
        if tmp == float('inf'):
            print(-1)
        else:
            print(tmp)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
stx = [list(map(int, input().split())) for _ in range(n)]
l = [int(input()) for _ in range(q)]

N = len(l)
LV = (N-1).bit_length()
N0 = 2**LV
data = [float('inf')]*(2*N0)
lazy = [None]*(2*N0)

# 伝搬対象の区間を求める
def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if v is None:
            continue
        lazy[2*i-1] = data[2*i-1] = lazy[2*i] = data[2*i] = v
        lazy[i-1] = None

# 区間[l, r)をxで更新
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] = data[R-1] = x
        if L & 1:
            lazy[L-1] = data[L-1] = x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = float('inf')
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

from bisect import bisect_left

stx.sort(key=lambda x:x[2], reverse=True)
for s, t, x in stx:
    i1 = bisect_left(l, s - 0.5 - x)
    i2 = bisect_left(l, t - 0.5 - x)
    update(i1, i2, x)

for i in range(q):
    tmp = query(i, i+1)
    if tmp == float('inf'):
        print(-1)
    else:
        print(tmp)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify,heappop,heappush
import sys
read=sys.stdin.readline
class mset:
    def __init__(self):
        self.p,self.q=[],[]
        heapify(self.p);heapify(self.q)
    def add(self,a):
        heappush(self.p,a)
    def delete(self,a):
            heappush(self.q,a)
    def minimum(self):
        while self.q and self.p[0]==self.q[0]:
            heappop(self.p);heappop(self.q)
        return self.p[0] if self.p else None

N,Q=map(int,read().split())
event=[]
for i in range(N):
    S,T,X=map(int,read().split())
    event.append((1,S-X,X))
    event.append((0,T-X,X))

s=mset()
now=0
for i in range(Q):
    D=int(read())
    event.append((2,D,0))
event.sort(key=lambda x:(x[1],x[0]))

for c,t,w in event:
    if c==0:
        s.delete(w)
    elif c==1:
        s.add(w)
    else:
        m=s.minimum()
        print(-1 if m==None else m)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify,heappop,heappush
import sys
read=sys.stdin.readline
class mset:
    def __init__(self):
        self.p,self.q,self.dic=[],[],{}
        heapify(self.p);heapify(self.q)
    def add(self,a):
        heappush(self.p,a)
        if not a in self.dic:
            self.dic[a]=1
        else:
            self.dic[a]+=1
    def delete(self,a):
        if a in self.dic and self.dic[a]>0:
            heappush(self.q,a)
            self.dic[a]-=1
    def search(self,a):
        return a in self.dic
    def minimum(self):
        while self.q and self.p[0]==self.q[0]:
            heappop(self.p);heappop(self.q)
        return self.p[0] if self.p else None

N,Q=map(int,read().split())
event=[]
for i in range(N):
    S,T,X=map(int,read().split())
    event.append((1,S-X,X))
    event.append((0,T-X,X))

s=mset()
now=0
for i in range(Q):
    D=int(input())
    event.append((2,D,0))
event.sort(key=lambda x:(x[1],x[0]))

for c,t,w in event:
    if c==0:
        s.delete(w)
    elif c==1:
        s.add(w)
    else:
        m=s.minimum()
        print(-1 if m==None else m)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify,heappop,heappush
import sys
read=sys.stdin.readline
class mset:
    def __init__(self):
        self.p,self.q,self.dic=[],[],{}
        heapify(self.p);heapify(self.q)
    def add(self,a):
        heappush(self.p,a)
        if not a in self.dic:
            self.dic[a]=1
        else:
            self.dic[a]+=1
    def delete(self,a):
        if a in self.dic and self.dic[a]>0:
            heappush(self.q,a)
            self.dic[a]-=1
    def search(self,a):
        return a in self.dic
    def minimum(self):
        while self.q and self.p[0]==self.q[0]:
            heappop(self.p);heappop(self.q)
        return self.p[0] if self.p else None

N,Q=map(int,read().split())
event=[]
for i in range(N):
    S,T,X=map(int,read().split())
    event.append((1,S-X,X))
    event.append((0,T-X,X))
event.sort(key=lambda x:x[1])

s=mset()
now=0
for i in range(Q):
    D=int(read())
    while(now<len(event) and event[now][1]<=D):
        if event[now][0]==1:
            s.add(event[now][2])
        elif event[now][0]==0:
            s.delete(event[now][2])
        now+=1
    m=s.minimum()
    print(-1 if m==None else m)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify,heappop,heappush
class mset:
    def __init__(self):
        self.p,self.q,self.dic=[],[],{}
        heapify(self.p);heapify(self.q)
    def add(self,a):
        heappush(self.p,a)
        if not a in self.dic:
            self.dic[a]=1
        else:
            self.dic[a]+=1
    def delete(self,a):
        if a in self.dic and self.dic[a]>0:
            heappush(self.q,a)
            self.dic[a]-=1
    def search(self,a):
        return a in self.dic
    def minimum(self):
        while self.q and self.p[0]==self.q[0]:
            heappop(self.p);heappop(self.q)
        return self.p[0] if self.p else None

N,Q=map(int,input().split())
event=[]
for i in range(N):
    S,T,X=map(int,input().split())
    event.append((1,S-X,X))
    event.append((0,T-X,X))
event.sort(key=lambda x:x[1])

s=mset()
now=0
for i in range(Q):
    D=int(input())
    while(now<len(event) and event[now][1]<=D):
        if event[now][0]==1:
            s.add(event[now][2])
        elif event[now][0]==0:
            s.delete(event[now][2])
        now+=1
    m=s.minimum()
    print(-1 if m==None else m)

Submission status: Time Limit Exceeded

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():
    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)}
    l=[]
    for i in range(N):
        l.append((S[i]-X[i],1,d[X[i]]))
        l.append((T[i]-X[i],-1,d[X[i]]))
    for i in range(Q):
        l.append((int(input()),2,0))
    l.sort(key=lambda t: t[0])
    b=BIT(len(unique_X))
    for t,q,x in l:
        if q==-1:
            b.add(x,-1)
        elif q==1:
            b.add(x,1)
        else:
            res,_=b.lower_bound(1)
            print(unique_X[res] if res<len(unique_X) else -1)
        


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline # 入出力高速化

class BIT:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = N.bit_length()

    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret

    def bitsum(self, l, r=None):
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)

    def bitadd(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        v = 1 << self.depth
        for i in range(self.depth, -1, -1):
            k = pos + v
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += v
            v >>= 1
        return pos

def main():
    N, Q = map(int, input().split())
    tl = list() # イベントタイムライン
    points = list()
    for _ in range(N):
        S, T, X = map(int, input().split())
        tl.append((S-X, 1, X)) # insert
        tl.append((T-X, 0, X)) # erase
        points.append(X)
        
    for _ in range(Q):
        D = int(input())
        tl.append((D, 2, 0)) # min
    
    tl.sort()
    points.sort()
    M = len(points)
    comp = {e:i for i, e in enumerate(points)} # 座標圧縮
    B = BIT(M + 20)
 
    for t, c, x in tl:
        if c == 0: # erase
            B.bitadd(comp[x], -1)
        elif c == 1: # insert
            B.bitadd(comp[x], 1)
        else: # min
            idx = B.lower_bound(1)
            print(-1 if idx > M + 10 else points[idx])
    return
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq

def main():
    N, Q = map(int, input().split())
    tl = [] # イベントタイムライン
    for _ in range(N):
        S, T, X = map(int, input().split())
        tl.append((S-X, 1, X)) # insert
        tl.append((T-X, 0, X)) # erase
    for _ in range(Q):
        D = int(input())
        tl.append((D, 2, 0)) # min
    tl.sort()
    working = [10**18] # 工事中、無限遠点を入れておく
    todelete = list() # 削除用
    for t, c, x in tl:
        if c == 0: # erase
            heapq.heappush(todelete, x)
        elif c == 1: # insert
            heapq.heappush(working, x)
        else: # min
            while todelete and todelete[0] == working[0]:
                heapq.heappop(todelete)
                heapq.heappop(working)
            print(-1 if working[0] == 10**18 else working[0])
    return
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    n, q = map(int, input().split())
    X = []
    stx = []
    tmp = set([])

    for _ in range(n):
        s,t,x = map(int, input().split())
        stx.append((s,t,x))
        tmp.add(x-t)
        tmp.add(x-s)

    d = {}
    for i in range(q):
        di = -int(input())
        tmp.add(di)
        d[di] = i

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

    v2i = {}

    for i, v in enumerate(sorted(tmp)):
        v2i[v] = i

    l = [1] * (len(tmp) + 1)

    for di in d:
        l[v2i[di]] = di
            

    #####単位元######
    ide_ele_min = 1

    #num_min:n以上の最小の2のべき乗
    N = len(l)

    num_min =2**(N-1).bit_length()
    seg_min=[ide_ele_min]*2*num_min

    def init_min(init_min_val):
        #set_val
        for i in range(N):
            seg_min[i+num_min-1]=init_min_val[i]    
        #built
        for i in range(num_min-2,-1,-1) :
            seg_min[i]=min(seg_min[2*i+1],seg_min[2*i+2]) 
    
    def update_min(k,x):
        k += num_min-1
        seg_min[k] = x
        while k:
            k = (k-1)//2
            seg_min[k] = min(seg_min[k*2+1],seg_min[k*2+2])
        
    def query_min(p,q):
        if q<=p:
            return ide_ele_min
        p += num_min-1
        q += num_min-2
        res=ide_ele_min
        while q-p>1:
            if p&1 == 0:
                res = min(res,seg_min[p])
            if q&1 == 1:
                res = min(res,seg_min[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = min(res,seg_min[p])
        else:
            res = min(min(res,seg_min[p]),seg_min[q])
        return res



    init_min(l)
    ans = {}

    for s, t, x in stx:
        l = v2i[x-t] + 1
        r = v2i[x-s] + 1
        v = query_min(l, r)
        while v != 1:
            i_d = d[v]
            i_sg = v2i[v]
            ans[i_d] = x
            update_min(i_sg, 1)
            v = query_min(l, r)

    for i in range(q):
        if i in ans:
            print(ans[i])
        else:
            print(-1)
            
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from operator import itemgetter
    input = sys.stdin.readline

    n, q = map(int, input().split())
    X = []
    stx = []
    tmp = set([])

    for _ in range(n):
        s,t,x = map(int, input().split())
        stx.append((s,t,x))
        X.append((x, _))
        tmp.add(x-t)
        tmp.add(x-s)

    d = {}
    for i in range(q):
        di = -int(input())
        tmp.add(di)
        d[di] = i

    X.sort(key = itemgetter(0))

    v2i = {}

    for i, v in enumerate(sorted(tmp)):
        v2i[v] = i

    l = [1] * (len(tmp) + 1)

    for di in d:
        l[v2i[di]] = di
            

    #####単位元######
    ide_ele_min = 1

    #num_min:n以上の最小の2のべき乗
    N = len(l)

    num_min =2**(N-1).bit_length()
    seg_min=[ide_ele_min]*2*num_min

    def init_min(init_min_val):
        #set_val
        for i in range(N):
            seg_min[i+num_min-1]=init_min_val[i]    
        #built
        for i in range(num_min-2,-1,-1) :
            seg_min[i]=min(seg_min[2*i+1],seg_min[2*i+2]) 
    
    def update_min(k,x):
        k += num_min-1
        seg_min[k] = x
        while k:
            k = (k-1)//2
            seg_min[k] = min(seg_min[k*2+1],seg_min[k*2+2])
        
    def query_min(p,q):
        if q<=p:
            return ide_ele_min
        p += num_min-1
        q += num_min-2
        res=ide_ele_min
        while q-p>1:
            if p&1 == 0:
                res = min(res,seg_min[p])
            if q&1 == 1:
                res = min(res,seg_min[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = min(res,seg_min[p])
        else:
            res = min(min(res,seg_min[p]),seg_min[q])
        return res



    init_min(l)
    ans = {}
        
    for x, i in X:
        s, t, x = stx[i]
        l = v2i[x-t] + 1
        r = v2i[x-s] + 1
        v = query_min(l, r)
        while v != 1:
            i_d = d[v]
            i_sg = v2i[v]
            ans[i_d] = x
            update_min(i_sg, 1)
            v = query_min(l, r)

    for i in range(q):
        if i in ans:
            print(ans[i])
        else:
            print(-1)
            
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from operator import itemgetter
    input = sys.stdin.readline

    class SegTree():
        def __init__(self, A):
            n_ = len(A)
            self.n = 1
            while self.n < n_:
                self.n *= 2
            self.tree = [1] * (2 * self.n - 1)
            for k, a in enumerate(A):
                self.update(k, a)
        def update(self, k, a):
            k += self.n - 1
            self.tree[k] = a
            while k > 0:
                k = (k - 1) // 2
                self.tree[k] = min(self.tree[k * 2 + 1], self.tree[k * 2 + 2])
        def query(self, l, r):
            l += self.n - 1
            r += self.n - 2
            res = 1
            while r-l>1:
                if l&1 == 0:
                    res = min(res,self.tree[l])
                if r&1 == 1:
                    res = min(res,self.tree[r])
                    r -= 1
                l = l//2
                r = (r-1)//2
            if l == r:
                res = min(res,self.tree[l])
            else:
                res = min(min(res,self.tree[l]),self.tree[r])
            return res

    n, q = map(int, input().split())
    X = []
    stx = []
    tmp = set([])

    for _ in range(n):
        s,t,x = map(int, input().split())
        stx.append((s,t,x))
        X.append((x, _))
        tmp.add(x-t)
        tmp.add(x-s)

    d = {}
    for i in range(q):
        di = -int(input())
        tmp.add(di)
        d[di] = i

    X.sort(key = itemgetter(0))

    v2i = {}

    for i, v in enumerate(sorted(tmp)):
        v2i[v] = i

    l = [1] * (len(tmp) + 1)

    for di in d:
        l[v2i[di]] = di
            
    sgt = SegTree(l)
    ans = {}

    sgt_update = sgt.update
    sgt_query = sgt.query
        
    for x, i in X:
        s, t, x = stx[i]
        l = v2i[x-t] + 1
        r = v2i[x-s] + 1
        v = sgt_query(l, r)
        while v != 1:
            i_d = d[v]
            i_sg = v2i[v]
            ans[i_d] = x
            sgt_update(i_sg, 1)
            v = sgt_query(l, r)

    for i in range(q):
        if i in ans:
            print(ans[i])
        else:
            print(-1)
            
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from operator import itemgetter
    input = sys.stdin.readline

    class SegTree():
        def __init__(self, A):
            n_ = len(A)
            self.n = 1
            while self.n < n_:
                self.n *= 2
            self.tree = [1] * (2 * self.n - 1)
            for k, a in enumerate(A):
                self.update(k, a)
        def update(self, k, a):
            k += self.n - 1
            self.tree[k] = a
            while k > 0:
                k = (k - 1) // 2
                self.tree[k] = min(self.tree[k * 2 + 1], self.tree[k * 2 + 2])
        def query(self, l, r):
            l += self.n - 1
            r += self.n - 2
            res = 1
            while r-l>1:
                if l&1 == 0:
                    res = min(res,self.tree[l])
                if r&1 == 1:
                    res = min(res,self.tree[r])
                    r -= 1
                l = l//2
                r = (r-1)//2
            if l == r:
                res = min(res,self.tree[l])
            else:
                res = min(min(res,self.tree[l]),self.tree[r])
            return res

    n, q = map(int, input().split())
    stx = []
    tmp = set([])

    for _ in range(n):
        s,t,x = map(int, input().split())
        stx.append((s,t,x))
        tmp.add(x-t)
        tmp.add(x-s)

    d = {}
    for i in range(q):
        di = -int(input())
        tmp.add(di)
        d[di] = i

    stx.sort(key = itemgetter(2))

    v2i = {}

    for i, v in enumerate(sorted(tmp)):
        v2i[v] = i

    l = [1] * (len(tmp) + 1)

    for di in d:
        l[v2i[di]] = di
            
    sgt = SegTree(l)
    ans = {}

    sgt_update = sgt.update
    sgt_query = sgt.query
        
    for s, t, x in stx:
        l = v2i[x-t] + 1
        r = v2i[x-s] + 1
        v = sgt_query(l, r)
        while v != 1:
            i_d = d[v]
            i_sg = v2i[v]
            ans[i_d] = x
            sgt_update(i_sg, 1)
            v = sgt_query(l, r)

    for i in range(q):
        if i in ans:
            print(ans[i])
        else:
            print(-1)
            
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from operator import itemgetter
    input = sys.stdin.readline

    class SegTree():
        def __init__(self, A):
            n_ = len(A)
            self.n = 1
            while self.n < n_:
                self.n *= 2
            self.tree = [1] * (2 * self.n - 1)
            for k, a in enumerate(A):
                self.update(k, a)
        def update(self, k, a):
            k += self.n - 1
            self.tree[k] = a
            while k > 0:
                k = (k - 1) // 2
                self.tree[k] = min(self.tree[k * 2 + 1], self.tree[k * 2 + 2])
        def query(self, l, r):
            l += self.n - 1
            r += self.n - 2
            res = 1
            while r-l>1:
                if l&1 == 0:
                    res = min(res,self.tree[l])
                if r&1 == 1:
                    res = min(res,self.tree[r])
                    r -= 1
                l = l//2
                r = (r-1)//2
            if l == r:
                res = min(res,self.tree[l])
            else:
                res = min(min(res,self.tree[l]),self.tree[r])
            return res

    n, q = map(int, input().split())
    stx = []
    tmp = set([])

    for _ in range(n):
        s,t,x = map(int, input().split())
        stx.append((s,t,x))
        tmp.add(x-t)
        tmp.add(x-s)

    d = {}
    for i in range(q):
        di = -int(input())
        tmp.add(di)
        d[di] = i

    stx.sort(key = itemgetter(2))

    v2i = {}
    tmp = list(tmp)
    tmp.sort()

    for i, v in enumerate(tmp):
        v2i[v] = i

    l = [1] * (len(tmp) + 1)

    for di in d:
        l[v2i[di]] = di
            
    sgt = SegTree(l)
    ans = {}

    sgt_update = sgt.update
    sgt_query = sgt.query
        
    for s, t, x in stx:
        l = v2i[x-t] + 1
        r = v2i[x-s] + 1
        v = sgt_query(l, r)
        while v != 1:
            i_d = d[v]
            i_sg = v2i[v]
            ans[i_d] = x
            sgt_update(i_sg, 1)
            v = sgt_query(l, r)

    for i in range(q):
        if i in ans:
            print(ans[i])
        else:
            print(-1)
            
if __name__ == '__main__':
    main()