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:
from heapq import heappush, heappop, merge
from collections import defaultdict

N, Q = map(int, input().split())
events = []
for _ in range(N):
    s, t, x = map(int, input().split())
    events.append((s-x, 1, x))
    events.append((t-x, -1, x))
events = sorted(events)

constructions = []
under_construction = defaultdict(bool)
i = 0
for _ in range(Q):
    d = int(input())
    while i < 2*N and events[i][0] <= d:
        if events[i][1] > 0:
            heappush(constructions, events[i][2])
            under_construction[events[i][2]] = True
        else:
            under_construction[events[i][2]] = False
        i += 1
    while constructions:
        x = heappop(constructions)
        if under_construction[x]: # x is the minimum coordinate under construction
            heappush(constructions, x)
            print(x)
            break
    else: # no constructions
        print(-1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, merge

N, Q = map(int, input().split())
events = []
for _ in range(N):
    s, t, x = map(int, input().split())
    events.append((s-x, 1, x))
    events.append((t-x, -1, x))
events = sorted(events)
constructions = []
i = 0
for _ in range(Q):
    d = int(input())
    while i < 2*N and events[i][0] <= d:
        if events[i][1] > 0:
            heappush(constructions, events[i][2])
        else:
            temp = []
            while constructions[0] != events[i][2]:
                heappush(temp, heappop(constructions))
            heappop(constructions)
            constructions = list(merge(temp, constructions))
        i += 1
    print(constructions[0] if constructions else -1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from numpy import int32,full,searchsorted
    s=searchsorted
    I=10**9+1
    n,q,*t=map(int,open(0).read().split())
    N0=2**(q-1).bit_length()
    data=full(2*N0,I,dtype='I')
    d=int32(t[-q:])
    t=int32(t[:-q])
    x=t[2::3]
    for x,l,r in sorted(zip(x,s(d,t[::3]-x)+N0,s(d,t[1::3]-x)+N0))[::-1]:
        while l<r:
            if r&1:
                r-=1
                data[r-1]=x
            if l&1:
                data[l-1]=x
                l+=1
            l>>=1
            r>>=1
    for k in range(N0-1,q+N0-1):
        s=I
        while~k:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        print(s if s<I else-1)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys

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

N, Q = list(map(int, next(sys.stdin).split()))
STX = [list(map(int, next(sys.stdin).split())) for _ in range(N)]
D = [int(next(sys.stdin)) for _ in range(Q)]


class LinkedNode:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next


ans = [-1 for _ in range(Q)]

last = LinkedNode(value=len(D) - 1)
unfixed = last
while unfixed.value > 0:
    unfixed = LinkedNode(value=unfixed.value - 1, next=unfixed)
# 最後から最初に戻れる
last.next = unfixed

prev = last
node = unfixed
for s, t, x in sorted(STX, key=lambda stx: (stx[2], stx[1])):
    # [lo, hi) に出発した人は x で止まる
    # x の小さい順にソート済みなのでここで確定
    lo = bisect.bisect_left(D, s - x)
    hi = bisect.bisect_left(D, t - x)
    start_value = node.value
    while node.next.value != start_value and lo <= node.value < hi:
        prev = node
        node = node.next
    start_value = node.value
    while node.next.value != start_value and not lo <= node.value < hi:
        prev = node
        node = node.next

    node_exists = True
    while lo <= node.value < hi:
        ans[node.value] = x
        # 確定したので LinkedList から消す
        if node.value != node.next.value:
            prev.next = node.next
            node = node.next
        else:
            # 全部消えた
            node_exists = False
            break
    if not node_exists:
        break

for a in ans:
    print(int(a))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
events = []
for _ in range(N):
    s, t, x = map(int, input().split())
    events.append((s-x, 1, x))
    events.append((t-x, -1, x))
events = sorted(events)
constructions = set([])
i = 0
for _ in range(Q):
    d = int(input())
    while i < 2*N and events[i][0] <= d:
        if events[i][1] > 0:
            constructions |= {events[i][2]}
        else:
            constructions -= {events[i][2]}
        i += 1
    print(min(constructions) if constructions else -1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import*
import sys;input=sys.stdin.readline

def doevent(lis):
    global stop
    a,b=lis
    if b>=0:
        if stop=={-1}:
            stop=set()
        stop.add(b)
    else:
        if -b in stop:
            stop.remove(-b)
        if stop==set():
            stop={-1}
    return min(stop)

stop=set([-1])
def main():
    n,q=map(int,input().split())
    event=[]
    
    for i in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,x))
        event.append((t-x,-x))
    event.sort(key=lambda x:x[0])
    minlist=[doevent(i)for i in event] #時間をindexとしたminlist

    for i in range(q):
        sys.stdout.writelines(str(minlist[bisect_right(event,(int(input()),10**9))-1])+"\n")
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import*
import sys;input=sys.stdin.readline

def doevent(lis):
    global stop
    a,b=lis
    if b>=0:
        if stop=={-1}:
            stop=set()
        stop.add(b)
    else:
        if -b in stop:
            stop.remove(-b)
        if stop==set():
            stop={-1}
    return min(stop)

stop=set([-1])
def main():
    n,q=map(int,input().split())
    event=[]
    
    for i in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,x))
        event.append((t-x,-x))
    event.sort(key=lambda x:x[0])
    minlist=[doevent(i)for i in event] #時間をindexとしたminlist

    for i in range(q):
        sys.stdout.writelines(str(minlist[bisect_right(event,(int(input()),10**9))-1])+"\n")
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import*
import sys;input=sys.stdin.readline

def doevent(lis):
    global stop
    a,b=lis
    if b>=0:
        if stop=={-1}:
            stop=set()
        stop.add(b)
    else:
        if -b in stop:
            stop.remove(-b)
        if stop==set():
            stop={-1}
    return min(stop)

stop=set([-1])
def main():
    n,q=map(int,input().split())
    event=[]
    
    for i in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,x))
        event.append((t-x,-x))
    event.sort(key=lambda x:x[0])
    minlist=[doevent(i)for i in event] #時間をindexとしたminlist

    for i in range(q):
        print(minlist[bisect_right(event,(int(input()),10**9))-1])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import*
import sys;input=sys.stdin.readline

def doevent(lis):
    global stop
    a,b=lis
    if b>=0:
        if stop=={-1}:
            stop=set()
        stop.add(b)
    else:
        if -b in stop:
            stop.remove(-b)
        if stop==set():
            stop={-1}
    return min(stop)

n,q=map(int,input().split())
event=[]
stop=set([-1])
def main():
    for i in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,x))
        event.append((t-x,-x))
    event.sort(key=lambda x:x[0])
    minlist=[doevent(i)for i in event] #時間をindexとしたminlist

    for i in range(q):
        print(minlist[bisect_right(event,(int(input()),10**9))-1])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import*
import sys;input=sys.stdin.readline

def doevent(lis):
    global stop
    a,b=lis
    if b>=0:
        if stop=={-1}:
            stop=set()
        stop.add(b)
    else:
        if -b in stop:
            stop.remove(-b)
        if stop==set():
            stop={-1}
    return min(stop)

n,q=map(int,input().split())
event=[]
stop=set([-1])

for i in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x,x))
    event.append((t-x,-x))
event.sort(key=lambda x:x[0])

minlist=[doevent(i)for i in event] #時間をindexとしたminlist

for i in range(q):
    print(minlist[bisect_right(event,(int(input()),10**9))-1])

Submission status: Time Limit Exceeded

Solution code:
from bisect import*
import sys;input=sys.stdin.readline

class doevent(object):
    def __init__(self):
        self.stop=set([-1])
    def do(self,lis):
        a,b=lis
        if b>=0:
            if self.stop=={-1}:
                self.stop=set()
            self.stop.add(b)
        else:
            if -b in self.stop:
                self.stop.remove(-b)
            if self.stop==set():
               self.stop={-1}
        return min(self.stop)

n,q=map(int,input().split())
event=[]
stop=set([-1])

for i in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x,x))
    event.append((t-x,-x))
event.sort(key=lambda x:x[0])

d=doevent()

minlist=[d.do(i)for i in event] #時間をindexとしたminlist

for i in range(q):
    print(minlist[bisect_right(event,(int(input()),float("inf")))-1])

Submission status: Time Limit Exceeded

Solution code:
import heapq
from collections import deque
N, Q = map( int, input().split())
H = [(0,0,0) for _ in range(N)]
for i in range(N):
    s, t, x = map( int, input().split())
    H[i] = (x-t+1, x-s, x)
D = [ ( -int( input()), i) for i in range(Q)]
D.sort()
H.sort()
d = deque(H)
q = []
ANS = [0]*Q
for i in range(Q):
    t, j = D[i]
    while d:
        if d[0][0] <= t:
            _, s, x = d.popleft()
            heapq.heappush(q,(x,s))
        else:
            break
    while q:
        if q[0][1] >= t:
            break
        heapq.heappop(q)
    if not q:
        ANS[j] = -1
    else:
        ANS[j] = q[0][0]
for ans in ANS:
    print( ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import*
import sys;input=sys.stdin.readline
import functools
@functools.lru_cache(maxsize=None)

def doevent(lis):
    global stop
    a,b=lis
    if b>=0:
        if stop=={-1}:
            stop=set()
        stop.add(b)
    else:
        if -b in stop:
            stop.remove(-b)
        if stop==set():
            stop={-1}
    return min(stop)

n,q=map(int,input().split())
event=[]
stop=set([-1])

for i in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x,x))
    event.append((t-x,-x))
event.sort(key=lambda x:x[0])

minlist=[doevent(i)for i in event] #時間をindexとしたminlist

for i in range(q):
    print(minlist[bisect_right(event,(int(input()),float("inf")))-1])

Submission status: Time Limit Exceeded

Solution code:
from bisect import*
import sys;input=sys.stdin.readline

n,q=map(int,input().split())
event=[]
stop=set([-1])

def doevent(lis):
    global stop
    a,b=lis
    if b>=0:
        if stop=={-1}:
            stop=set()
        stop.add(b)
    else:
        if -b in stop:
            stop.remove(-b)
        if stop==set():
            stop={-1}
    return min(stop)

for i in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x,x))
    event.append((t-x,-x))
event.sort(key=lambda x:x[0])

minlist=[doevent(i)for i in event] #時間をindexとしたminlist

for i in range(q):
    print(minlist[bisect_right(event,(int(input()),float("inf")))-1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline

## input
N,Q = map(int, readl().rstrip().split())
STX = [list(map(int, readl().rstrip().split())) for _ in range(N)]
Dn = [None for _ in range(Q+1)]
for i in range(Q):
  Dn[i] = int(readl().rstrip())
Dn[Q] = 10**10
Rn = []


## solve
for s,t,x in sorted(STX,key=lambda x:x[2]):
  l = r = bisect_left(Dn,s-x)
  t -= x
  while Dn[r] < t:
    Rn.append([Dn[r],x])
    r += 1
  del Dn[l:r]

for d in Dn[:-1]:
  Rn.append([d,-1])
Rn.sort()


## output
for i in range(Q):
  print(Rn[i][1])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline

## input
N,Q = map(int, readl().rstrip().split())
STX = [list(map(int, readl().rstrip().split())) for _ in range(N)]
Dn = [None for _ in range(Q+1)]
for i in range(Q):
  Dn[i] = int(readl().rstrip())
Dn[Q] = 10**10
ans = []


## solve
for s,t,x in sorted(STX,key=lambda x:x[2]):
  l = r = bisect_left(Dn,s-x)
  t -= x
  while Dn[r] < t:
    heappush(ans, (Dn[r],x))
    r += 1
  del Dn[l:r]

for d in Dn[:-1]:
  heappush(ans, (d,-1))


## output
for _ in range(Q):
  print(heappop(ans)[1])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    event = []
    for i in range(N):
        s, t, x = map(int, line_input())
        event.append((max(s-x, -1), 1, x))
        event.append((max(t-x, 0), -1, x))
    for i in range(Q):
        d = int(single_input())
        event.append((d, 2, d))
    event.sort()
    stop = set()
    ans = ""
    for time, parameter, co in event:
        if parameter == 1: stop |= {co}
        elif parameter == -1: stop -= {co}
        else:
            if stop:
                ans += str(min(stop)) + "\n"
            else: ans += "-1\n"
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [list(map(int,inputs().split())) for p in [0]*N]

for q in [0]*Q:
	ans = sys.maxsize
	m = int(inputs())
	for n in range(N):
		if V[n][0] - V[n][2] <=m and m <= V[n][1] - V[n][2] -1:
			ans = min(V[n][2],ans)
	if ans < sys.maxsize:
		print(ans)
	else:
		print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [list(map(int,inputs().split())) for p in [0]*N]
V.sort(key = lambda x:(x[2]))

for q in [0]*Q:
	m = int(inputs())
	for n in range(N):
		if V[n][0] - V[n][2] <=m and m <= V[n][1] - V[n][2] -1:
			print(V[n][2])
			break
	else:
		print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [list(map(int,inputs().split())) for p in [0]*N]
M = [int(inputs()) for p in [0]*Q]
V.sort(key = lambda x:(x[2]))

for m in M:
	for n in range(N):
		if V[n][0] - V[n][2] <=m and m <= V[n][1] - V[n][2] -1:
			print(V[n][2])
			break
	else:
		print(-1)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [list(map(int,inputs().split())) for p in [0]*N]
M = [int(inputs()) for p in [0]*Q]
V.sort(key = lambda x:(x[2],x[0],x[1]))

for v in V:
	v[0] -= v[2]
	v[1] -= v[2] + 1
for m in M:
	for n in range(N):
		if V[n][0] <=m and m <= V[n][1]:
			print(V[n][2])
			break
	else:
		print(-1)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [list(map(int,inputs().split())) for p in [0]*N]
M = [int(inputs()) for p in [0]*Q]
V.sort(key = lambda x:(x[2],x[0],x[1]))

W = []
for v in V:
	W.append([v[0]-v[2],v[1]-v[2]-1])
w = W[:]
for m in M:
	for n in range(N):
		w[n].append(m)
		w[n].sort()
		if w[n][1] == m:
			print(V[n][2])
			w[n].remove(m)
			break
		w[n].remove(m)
	else:
		print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
def main():
  N, Q = list(map(int, input().split()))
  STX = tuple(list(map(int, input().split())) for _ in range(N))
  D = tuple([int(input()) for _ in range(Q)])

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

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

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import heapq as hq
  N, Q = list(map(int, input().split()))
  STX = tuple(list(map(int, input().split())) for _ in range(N))
  D = tuple([int(input()) for _ in range(Q)])

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

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

main()

Submission status: Time Limit Exceeded

Solution code:
import heapq as hq
def main():
  N, Q = list(map(int, input().split()))
  STX = [list(map(int, input().split())) for _ in range(N)]
  D = [int(input()) for _ in range(Q)]

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

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

main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
cs = []
for _ in range(N):
  s, t, x = map(int, input().split())
  cs.append((x, s, t))

cs.sort()
ds = [ int(input()) for _ in range(Q) ]

for d in ds:
  for x, s, t in cs:
    if s-0.5 <= d + x and d + x <= t - 0.5:
      print(x)
      break
  else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq as hq

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
  import heapq as hq
  N, Q = list(map(int, input().split()))
  STX = [list(map(int, input().split())) for _ in range(N)]
  D = [int(input()) for _ in range(Q)]

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

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

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import heapq as hq
  N, Q = list(map(int, input().split()))
  STX = [list(map(int, input().split())) for _ in range(N)]
  D = [int(input()) for _ in range(Q)]

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

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

main()