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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    def sum(self, i):  # 区間 [1, i]の和
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def add(self, i, x):  # iにxを加算
        while i <= self.size:
            self.tree[i] += x
            i += i & -i  
    def pos(self, idx):  # idxの値を取得
        return self.sum(idx) - self.sum(idx-1)
    def lower_bound(self, w):  # w以上の値を持つ最小のidxを検索
        if w <= 0:
            return 0
        idx = 0
        k = 1
        while k*2 <= self.size:
            k *= 2
        while k > 0:
            if idx+k <= self.size and self.tree[idx+k] < w:
                w -= self.tree[idx+k]
                idx += k
            k //= 2
        return idx+1

N, Q = MAP()

event = [None]*(2*N+Q)
Xl = [0]*N
for i in range(N):
	S, T, X = MAP()
	event[2*i] = (S-X, 1, X)
	event[2*i+1] = (T-X, 0, X)
	Xl[i] = X

t = 2*N
for i in range(Q):
	D = INT()
	event[t+i] = (D, 2, 0)

event.sort()
len_X = len(Xl)
Xl.sort()
zipped = {e:i for i, e in enumerate(Xl)}
bit = Bit(len_X+1)

for t, c, x in event:
	if c == 0:
		bit.add(zipped[x], -1)
	elif c == 1:
		bit.add(zipped[x], 1)
	else:
		idx = bit.lower_bound(1)
		print(-1 if idx > len_X else Xl[idx])

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:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def main():
    N, Q = lr()
    STX = [tuple(lr()) for _ in range(N)]
    event = []
    for s, t, x in STX:
        event.append((s-x, 0, x))
        event.append((t-x, -1, x))

    for i in range(Q):
        d = ir()
        event.append((d, 1, i))

    event.sort()
    answer = [-1] * Q
    cur = set()
    flag = False
    INF = 10 ** 10
    min_x = INF
    for a, b, c in event:
        if b == 0:
            cur.add(c)
            if c < min_x:
                min_x = c
                flag = True
        elif b == -1:
            cur.remove(c)
            if min_x == c:
                flag = False
        elif b == 1:
            if cur:
                if not flag:
                    min_x = min(cur)
                    flag = True
                answer[c] = min_x

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
STX = [tuple(lr()) for _ in range(N)]
event = []
for s, t, x in STX:
    event.append((s-x, 0, x))
    event.append((t-x, -1, x))

for i in range(Q):
    d = ir()
    event.append((d, 1, i))

event.sort()
answer = [-1] * Q
cur = set()
flag = False
INF = 10 ** 10
min_x = INF
for a, b, c in event:
    if b == 0:
        cur.add(c)
        if c < min_x:
            min_x = c
            flag = True
    elif b == -1:
        cur.remove(c)
        if min_x == c:
            flag = False
    elif b == 1:
        if cur:
            if not flag:
                min_x = min(cur)
                flag = True
            answer[c] = min_x

print('\n'.join(map(str, answer)))
# 19

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
STX = [tuple(lr()) for _ in range(N)]
STX.sort(key=lambda x: x[2], reverse=True)
event = []
for s, t, x in STX:
    event.append((s-x, 0, x))
    event.append((t-x, -1, x))

for i in range(Q):
    d = ir()
    event.append((d, 1, i))

event.sort()
answer = [-1] * Q
cur = set()
flag = False
INF = 10 ** 10
min_x = INF
for a, b, c in event:
    if b == 0:
        cur.add(c)
        if c < min_x:
            min_x = c
            flag = True
    elif b == -1:
        cur.remove(c)
        if min_x == c:
            flag = False
    elif b == 1:
        if cur:
            if not flag:
                min_x = min(cur)
                flag = True
            answer[c] = min_x

print('\n'.join(map(str, answer)))
# 19

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
STX = [tuple(lr()) for _ in range(N)]
STX.sort(key=lambda x: x[2], reverse=True)
event = []
for s, t, x in STX:
    s = max(-1, s-x)
    t = max(0, t-x)
    event.append((s, 0, x))
    event.append((t, -1, x))

answer = [None] * Q
for i in range(Q):
    d = ir()
    event.append((d, 1, i))

event.sort()
cur = []
used = set()
for a, b, c in event:
    if b == 0:
        if c in used:
            used.remove(c)
        heappush(cur, c)
    elif b == -1:
        used.add(c)
    elif b == 1:
        while cur and cur[0] in used:
            heappop(cur)
        if cur:
            answer[c] = cur[0]
        else:
            answer[c] = -1

print('\n'.join(map(str, answer)))
# 19

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
STX = [tuple(lr()) for _ in range(N)]
STX.sort(key=lambda x: x[2], reverse=True)
event = []
for s, t, x in STX:
    s = max(-1, s-x)
    t = max(0, t-x)
    event.append((s, 0, x))
    event.append((t, -1, x))

answer = [None] * Q
for i in range(Q):
    d = ir()
    event.append((d, 1, i))

event.sort(key=lambda x: [x[0], x[1]])
cur = []
used = set()
for a, b, c in event:
    if b == 0:
        if c in used:
            used.remove(c)
        heappush(cur, c)
    elif b == -1:
        used.add(c)
    elif b == 1:
        while cur and cur[0] in used:
            heappop(cur)
        if cur:
            answer[c] = cur[0]
        else:
            answer[c] = -1

print('\n'.join(map(str, answer)))
# 19

Submission status: Time Limit Exceeded

Solution code:
def main():
    import os
    import sys
    from io import BytesIO, IOBase
    
    BUFSIZE = 8192
    
    
    class FastIO(IOBase):
        newlines = 0
    
        def __init__(self, file):
            self._fd = file.fileno()
            self.buffer = BytesIO()
            self.writable = "x" in file.mode or "r" not in file.mode
            self.write = self.buffer.write if self.writable else None
    
        def read(self):
            while True:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                if not b:
                    break
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines = 0
            return self.buffer.read()
    
        def readline(self):
            while self.newlines == 0:
                b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                self.newlines = b.count(b"\n") + (not b)
                ptr = self.buffer.tell()
                self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
            self.newlines -= 1
            return self.buffer.readline()
    
        def flush(self):
            if self.writable:
                os.write(self._fd, self.buffer.getvalue())
                self.buffer.truncate(0), self.buffer.seek(0)
    
    
    class IOWrapper(IOBase):
        def __init__(self, file):
            self.buffer = FastIO(file)
            self.flush = self.buffer.flush
            self.writable = self.buffer.writable
            self.write = lambda s: self.buffer.write(s.encode("ascii"))
            self.read = lambda: self.buffer.read().decode("ascii")
            self.readline = lambda: self.buffer.readline().decode("ascii")
    
    
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
    input = lambda: sys.stdin.readline().rstrip("\r\n")
    mod = 10**9 + 7

    from heapq import heappush, heappop 

    running = [] # 止まりうる座標
    events = [] # 時刻順のイベント
    finished = set() # 工事が終了した座標

    n, q = map(int, input().split())
    for _ in range(n):
        s, t, x = map(int, input().split())
        events.append((s - x, x, 1)) # 追加イベント
        events.append((t - x, x, 0)) # 削除イベント
    for _ in range(q):
        d = int(input())
        events.append((d, 10**10, 2)) # 出発イベント,同じ時刻内で最後になるよう第二引数設定
    events.sort()
    for i in range(len(events)):
        temp = events[i]
        if temp[-1] == 1:
            heappush(running, temp[1])
            finished.discard(temp[1])
        elif temp[-1] == 0:
            finished.add(temp[1])
        else:
            flag = 1
            while running:
                p = heappop(running)
                if p not in finished:
                    flag = 0
                    heappush(running, p)
                    print(p)
                    break
            if flag:
                print(-1)
main()

Submission status: Time Limit Exceeded

Solution code:

import os
import sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
mod = 10**9 + 7

from heapq import heappush, heappop 

running = [] # 止まりうる座標
events = [] # 時刻順のイベント
finished = set() # 工事が終了した座標

n, q = map(int, input().split())
for _ in range(n):
    s, t, x = map(int, input().split())
    events.append((s - x, x, 1)) # 追加イベント
    events.append((t - x, x, 0)) # 削除イベント
for _ in range(q):
    d = int(input())
    events.append((d, 10**10, 2)) # 出発イベント,同じ時刻内で最後になるよう第二引数設定
events.sort()
for i in range(len(events)):
    temp = events[i]
    if temp[-1] == 1:
        heappush(running, temp[1])
        finished.discard(temp[1])
    elif temp[-1] == 0:
        finished.add(temp[1])
    else:
        flag = 1
        while running:
            p = heappop(running)
            if p not in finished:
                flag = 0
                heappush(running, p)
                print(p)
                break
        if flag:
            print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq

def main():
    n,q = readints()

    a = []
    for i in range(n):
        s,t,x = readints()
        a.append((s-x,0,x))
        a.append((t-x,1,x))
    for i in range(q):
        d = readint()
        a.append((d,2,0))
    a.sort()

    ans = []

    stop = []
    deleted = []

    for t,j,x in a:
        if j==0:
            heapq.heappush(stop,x)
        elif j==1:
            heapq.heappush(deleted,x)
        else:
            while deleted and stop[0] == deleted[0]:
                heapq.heappop(stop)
                heapq.heappop(deleted)
            if stop:
                ans.append(stop[0])
            else:
                ans.append(-1)

    printrows(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq

n,q = readints()

a = []
for i in range(n):
    s,t,x = readints()
    a.append((s-x,0,x))
    a.append((t-x,1,x))
for i in range(q):
    d = readint()
    a.append((d,2,0))
a.sort()

ans = []

stop = []
deleted = []

for t,j,x in a:
    if j==0:
        heapq.heappush(stop,x)
    elif j==1:
        heapq.heappush(deleted,x)
    else:
        while deleted and stop[0] == deleted[0]:
            heapq.heappop(stop)
            heapq.heappop(deleted)
        if stop:
            ans.append(stop[0])
        else:
            ans.append(-1)

printrows(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq

n,q = readints()

a = []
for i in range(n):
    s,t,x = readints()
    a.append((s-x,x,0))
    a.append((t-x,x,1))
for i in range(q):
    d = readint()
    a.append((d,10**10,2))
a.sort()

ans = []

stop = []
deleted = []

for t,x,j in a:
    if j==0:
        heapq.heappush(stop,x)
    elif j==1:
        heapq.heappush(deleted,x)
    else:
        while deleted and stop[0] == deleted[0]:
            heapq.heappop(stop)
            heapq.heappop(deleted)
        if stop:
            ans.append(stop[0])
        else:
            ans.append(-1)

printrows(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


def compress(a):
    b = sorted(set(a))
    d = {x:i+1 for i,x in enumerate(b)}
    return b,d


import heapq

n,q = readints()

X = []

a = []
for i in range(n):
    s,t,x = readints()
    X.append(x)
    a.append((s-x,x,1))
    a.append((t-x,x,0))

a.sort()

ans = []

stop = []
heapq.heapify(stop)
deleted = []
heapq.heapify(deleted)

j = 0
for i in range(q):
    D = readint()
    while j<2*n and a[j][0] <= D:
        if a[j][2]:
            heapq.heappush(stop,a[j][1])
        else:
            heapq.heappush(deleted,a[j][1])
        j+=1

    while deleted:
        if stop[0] == deleted[0]:
            heapq.heappop(stop)
            heapq.heappop(deleted)
        else:
            break
    if stop:
        ans.append(stop[0])
    else:
        ans.append(-1)

printrows(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


class AVL_like_BIT:  # 1-indexed
    def __init__(self,n):  # 1~nを要素として持ちうる。
        self.n = n
        self.tree = [0]*(self.n+1)
        self.depth = n.bit_length()

    def add(self,k):  # kを木に加える
        while k<=self.n:
            self.tree[k]+=1
            k += k&-k
    
    def delete(self,k): # kを木から削除する
        while k<=self.n:
            self.tree[k]-=1
            k += k&-k

    def sum(self,k):  # 1~kの和
        ans = 0
        while k>0:
            ans += self.tree[k]
            k -= k&-k
        return ans
    
    def lower_bound(self,k):  # k以上の最小要素
        x = self.sum(k-1)
        if x == self.sum(self.n):  # k以上の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = sum(k-1)なるpの右端 + 1が答え
            q = p+v
            if q <= self.n and self.tree[q] <= x:
                x -= self.tree[q]
                p += v
            v>>=1
        return p+1

    def upper_bound(self,k):  # k以下の最大要素
        x = self.sum(k)
        if x == 0:  # k以下の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = sum(k)なるpの左端が答え
            q = p+v
            if q <= self.n and self.tree[q] < x:
                x -= self.tree[q]
                p += v
            v>>=1
        return p+1

    def query(self,k):  # k番目の要素出力
        if k > self.sum(self.n):  # k個以上の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = kなるpの左端が答え
            q = p+v
            if q <= self.n and self.tree[q] < k:
                k -= self.tree[q]
                p += v
            v>>=1
        return p+1

def compress(a):
    b = sorted(set(a))
    d = {x:i+1 for i,x in enumerate(b)}
    return b,d


n,q = readints()

X = []

block = []
free = []
for i in range(n):
    s,t,x = readints()
    X.append(x)
    block.append([s-x,x])
    free.append([t-x,x])

b,d = compress(X)
block = [(x[0],d[x[1]]) for x in block]
free = [(x[0],d[x[1]]) for x in free]
block.sort()
free.sort()

ans = []
avl = AVL_like_BIT(len(d))
j = 0
k = 0
for i in range(q):
    D = readint()
    while j<n and block[j][0]<=D:
        avl.add(block[j][1])
        j+=1
    while k<n and free[k][0]<=D:
        avl.delete(free[k][1])
        k+=1
    ans.append(avl.lower_bound(0))

ans = [b[x-1] if x >=0 else -1 for x in ans]
printrows(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


class AVL_like_BIT:  # 1-indexed
    def __init__(self,n):  # 1~nを要素として持ちうる。
        self.n = n
        self.tree = [0]*(self.n+1)
        self.depth = n.bit_length()

    def add(self,k):  # kを木に加える
        while k<=self.n:
            self.tree[k]+=1
            k += k&-k
    
    def delete(self,k): # kを木から削除する
        while k<=self.n:
            self.tree[k]-=1
            k += k&-k

    def sum(self,k):  # 1~kの和
        ans = 0
        while k>0:
            ans += self.tree[k]
            k -= k&-k
        return ans
    
    def lower_bound(self,k):  # k以上の最小要素
        x = self.sum(k-1)
        if x == self.sum(self.n):  # k以上の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = sum(k-1)なるpの右端 + 1が答え
            q = p+v
            if q <= self.n and self.tree[q] <= x:
                x -= self.tree[q]
                p += v
            v>>=1
        return p+1

    def upper_bound(self,k):  # k以下の最大要素
        x = self.sum(k)
        if x == 0:  # k以下の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = sum(k)なるpの左端が答え
            q = p+v
            if q <= self.n and self.tree[q] < x:
                x -= self.tree[q]
                p += v
            v>>=1
        return p+1

    def query(self,k):  # k番目の要素出力
        if k > self.sum(self.n):  # k個以上の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = kなるpの左端が答え
            q = p+v
            if q <= self.n and self.tree[q] < k:
                k -= self.tree[q]
                p += v
            v>>=1
        return p+1

def compress(a):
    b = sorted(set(a))
    d = {x:i+1 for i,x in enumerate(b)}
    return b,d

n,q = readints()

X = []

a = []
for i in range(n):
    s,t,x = readints()
    X.append(x)
    a.append([s-x,x,1])
    a.append([t-x,x,0])

b,d = compress(X)
a = [(x[0],d[x[1]],x[2]) for x in a]
a.sort()

ans = []
avl = AVL_like_BIT(len(d))
k=0
for i in range(q):
    D = readint()
    for j in range(k,2*n):
        if a[j][0] <= D:
            if a[j][2]:
                avl.add(a[j][1])
            else:
                avl.delete(a[j][1])
            k = j+1
        else:
            k = j
            break
    ans.append(avl.lower_bound(0))

ans = [b[x-1] if x >=0 else -1 for x in ans]
printrows(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


class AVL_like_BIT:  # 1-indexed
    def __init__(self,n):  # 1~nを要素として持ちうる。
        self.n = n
        self.tree = [0]*(self.n+1)
        self.depth = n.bit_length()

    def add(self,k):  # kを木に加える
        while k<=self.n:
            self.tree[k]+=1
            k += k&-k
    
    def delete(self,k): # kを木から削除する
        while k<=self.n:
            self.tree[k]-=1
            k += k&-k

    def sum(self,k):  # 1~kの和
        ans = 0
        while k>0:
            ans += self.tree[k]
            k -= k&-k
        return ans
    
    def lower_bound(self,k):  # k以上の最小要素
        x = self.sum(k-1)
        if x == self.sum(self.n):  # k以上の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = sum(k-1)なるpの右端 + 1が答え
            q = p+v
            if q <= self.n and self.tree[q] <= x:
                x -= self.tree[q]
                p += v
            v>>=1
        return p+1

    def upper_bound(self,k):  # k以下の最大要素
        x = self.sum(k)
        if x == 0:  # k以下の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = sum(k)なるpの左端が答え
            q = p+v
            if q <= self.n and self.tree[q] < x:
                x -= self.tree[q]
                p += v
            v>>=1
        return p+1

    def query(self,k):  # k番目の要素出力
        if k > self.sum(self.n):  # k個以上の要素がないときは-1を返す
            return -1
        p = 0
        v = 1<<self.depth
        for i in range(self.depth + 1):  # sum(p) = kなるpの左端が答え
            q = p+v
            if q <= self.n and self.tree[q] < k:
                k -= self.tree[q]
                p += v
            v>>=1
        return p+1

def compress(a):
    b = sorted(set(a))
    d = {x:i+1 for i,x in enumerate(b)}
    return b,d

n,q = readints()

X = []

a = []
for i in range(n):
    s,t,x = readints()
    X.append(x)
    a.append([s-x,x,1])
    a.append([t-x,x,0])

b,d = compress(X)
a = [(x[0],d[x[1]],x[2]) for x in a]
a.sort()

ans = []
avl = AVL_like_BIT(len(d))
j=0
for i in range(q):
    D = readint()
    while j<2*n and a[j][0] <= D:
        if a[j][2]:
            avl.add(a[j][1])
        else:
            avl.delete(a[j][1])
        j+=1
    ans.append(avl.lower_bound(0))

ans = [b[x-1] if x >=0 else -1 for x in ans]
printrows(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


def compress(a):
    b = sorted(set(a))
    d = {x:i+1 for i,x in enumerate(b)}
    return b,d


import heapq

n,q = readints()

X = []

a = []
for i in range(n):
    s,t,x = readints()
    X.append(x)
    a.append([s-x,x,1])
    a.append([t-x,x,0])

b,d = compress(X)
a = [(x[0],d[x[1]],x[2]) for x in a]
a.sort()

ans = []

stop = []
heapq.heapify(stop)
deleted = []
heapq.heapify(deleted)

j = 0
for i in range(q):
    D = readint()
    while j<2*n and a[j][0] <= D:
        if a[j][2]:
            heapq.heappush(stop,a[j][1])
        else:
            heapq.heappush(deleted,a[j][1])
        j+=1

    while deleted:
        if stop[0] == deleted[0]:
            heapq.heappop(stop)
            heapq.heappop(deleted)
        else:
            break
    if stop:
        ans.append(stop[0])
    else:
        ans.append(-1)

ans = [b[x-1] if x >=0 else -1 for x in ans]
printrows(ans)