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
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


import heapq

n,q = readints()

X = []

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

b,d = compress(X)
stx = [(x[0],d[x[1]],x[2]) for x in stx]
heapq.heapify(stx)

ans = []
avl = AVL_like_BIT(len(d))
for i in range(q):
    D = readint()
    while stx:
        if stx[0][0]<=D:
            a = heapq.heappop(stx)
            if a[2]:
                avl.add(a[1])
            else:
                avl.delete(a[1])
        else:
            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:
from heapq import heappop, heappush
import numpy as np

import sys
input = sys.stdin.buffer.readline


def main():

    n, q = map(int, input().split())
    stx = [map(int, input().split()) for _ in range(n)]
    ds = [int(input()) for _ in range(q)]
    INF = 10 ** 9 + 1
    START = 1
    END = 0

    tfdi = []
    for i, (s, t, x) in enumerate(stx):
        t_start = max(0, s - x)
        t_end = max(0, t - x)
        if t_end == 0:
            continue

        tfdi.append((t_start, START, x, i))
        tfdi.append((t_end, END, x, i))

    tfdi.append((INF, START, INF, -1))
    tfdi.sort()

    hp = [(INF, -1)]
    ts = []
    dists = []
    t_prev = -1
    passed = set()
    for t, f, d, i in tfdi:
        if t != t_prev:
            ts.append(t_prev)
            while hp[0][1] in passed:
                heappop(hp)

            dists.append(hp[0][0])

        if f == START:
            heappush(hp, (d, i))
        else:
            passed.add(i)

        t_prev = t

    ts = np.array(ts, np.int64)
    ds = np.array(ds, np.int64)
    dists = np.array(dists, np.int64)

    idx = np.searchsorted(ts, ds, "right") - 1
    ans = dists[idx]
    ans[ans==INF] = -1
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
import numpy as np

import sys
input = sys.stdin.buffer.readline


def main():

    n, q = map(int, input().split())
    stx = [list(map(int, input().split())) for _ in range(n)]
    ds = [int(input()) for _ in range(q)]
    INF = 10 ** 18
    START = 1
    END = 0

    tfdi = []
    for i, (s, t, x) in enumerate(stx):
        t_start = max(0, s - x)
        t_end = max(0, t - x)
        if t_end == 0:
            continue

        tfdi.append([t_start, START, x, i])
        tfdi.append([t_end, END, x, i])

    tfdi.append([INF, START, INF, -1])
    tfdi.sort()

    hp = [[INF, -1]]
    ts = []
    dists = []
    t_prev = -1
    passed = set()
    for t, f, d, i in tfdi:
        if t != t_prev:
            ts.append(t_prev)
            while hp[0][1] in passed:
                heappop(hp)

            dists.append(hp[0][0])

        if f == START:
            heappush(hp, [d, i])
        else:
            passed.add(i)

        t_prev = t

    ts = np.array(ts, np.int64)
    ds = np.array(ds, np.int64)
    dists = np.array(dists, np.int64)

    idx = np.searchsorted(ts, ds, "right") - 1
    ans = dists[idx]
    ans[ans==INF] = -1
    print(*ans, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
from bisect import bisect_right
import numpy as np

n, q = map(int, input().split())
stx = [list(map(int, input().split())) for _ in range(n)]
ds = [int(input()) for _ in range(q)]
INF = 10 ** 18
START = 1
END = 0

tfdi = []
for i, (s, t, x) in enumerate(stx):
    t_start = max(0, s - x)
    t_end = max(0, t - x)
    if t_end == 0:
        continue

    tfdi.append([t_start, START, x, i])
    tfdi.append([t_end, END, x, i])

tfdi.append([INF, START, INF, -1])
tfdi.sort()

hp = [[INF, -1]]
ts = []
dists = []
t_prev = -1
passed = set()
for t, f, d, i in tfdi:
    if t != t_prev:
        ts.append(t_prev)
        while hp[0][1] in passed:
            heappop(hp)

        dists.append(hp[0][0])

    if f == START:
        heappush(hp, [d, i])
    else:
        passed.add(i)

    t_prev = t

ts = np.array(ts, np.int64)
ds = np.array(ds, np.int64)
dists = np.array(dists, np.int64)

idx = np.searchsorted(ts, ds, "right") - 1
ans = dists[idx]
ans[ans==INF] = -1
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush
from bisect import bisect_right

n, q = map(int, input().split())
stx = [list(map(int, input().split())) for _ in range(n)]
ds = [int(input()) for _ in range(q)]
INF = 10 ** 18
START = 1
END = 0

tfdi = []
for i, (s, t, x) in enumerate(stx):
    t_start = max(0, s - x)
    t_end = max(0, t - x)
    if t_end == 0:
        continue

    tfdi.append([t_start, START, x, i])
    tfdi.append([t_end, END, x, i])

tfdi.append([INF, START, INF, -1])
tfdi.sort()

hp = [[INF, -1]]
ts = []
dists = []
t_prev = -1
passed = set()
for t, f, d, i in tfdi:
    if t != t_prev:
        ts.append(t_prev)
        while hp[0][1] in passed:
            heappop(hp)

        dists.append(hp[0][0])

    if f == START:
        heappush(hp, [d, i])
    else:
        passed.add(i)

    t_prev = t

for d in ds:
    i = bisect_right(ts, d) - 1
    ans = dists[i]
    if ans == INF:
        ans = -1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

n, q = map(int, input().split())
stx = []
for _ in range(n):
    s, t, x = map(int, input().split())
    stx.append([x, s - x, t - x])
stx.sort(reverse=True)
d = [int(input()) for _ in range(q)]

# N: 処理する区間の長さ

INF = 10**9 + 1

n = q

Len = (n-1).bit_length()
size = 2**Len
tree = [INF]*(2*size)
lazy = [None]*(2*size)

def gindex(l,r):
    L = (l+size)>>1;R=(r+size)>>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(Len):
        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]
        if v is None:
            continue
        lazy[2*i]=tree[2*i]=lazy[2*i+1]=tree[2*i+1]=v
        lazy[i]=None

#[l,r)の探索
def update(l,r,x):
    *ids, = gindex(l, r)
    propagates(ids)
    
    L = size+l
    R = size+r
    while L<R:
        if R&1:
            R -= 1
            lazy[R]=tree[R]=x
        if L&1:
            lazy[L]=tree[L]=x
            L+=1
        L>>=1;R>>=1
    #値を更新し終わったら、最小値を下から更新
    for i in ids:
        if 2*i+1<size*2:
            tree[i]=min(tree[i*2],tree[i*2+1])
        
def query(l, r):
    *ids, = gindex(l, r)
    propagates(ids)
    L = size + l
    R = size + r
    s = INF
    while L<R:
        if R&1:
            R-=1
            s = min(s,tree[R])
        if L&1:
            s = min(s,tree[L])
            L+=1
        L>>=1;R>>=1
    return s

import bisect



for x, start, last in stx:
    l = bisect.bisect_left(d, start)
    r = bisect.bisect_left(d, last)
    update(l, r, x)

for i, j in enumerate(d):
    res = query(i, i + 1)
    if res == 10**9 + 1:
        print(-1)
    else:
        print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

n, q = map(int, input().split())
stx = []
for _ in range(n):
    s, t, x = map(int, input().split())
    stx.append([x, s - x, t - x])
stx.sort(reverse=True)
d = [int(input()) for _ in range(q)]

# N: 処理する区間の長さ

INF = 10**9 + 1
N = q
LV = (N-1).bit_length()
N0 = 2**LV
data = [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 = 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
import bisect



for x, start, last in stx:
    l = bisect.bisect_left(d, start)
    r = bisect.bisect_left(d, last)
    update(l, r, x)

for i, j in enumerate(d):
    res = query(i, i + 1)
    if res == 10**9 + 1:
        print(-1)
    else:
        print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

#####segfunc#####
def segfunc(x, y):
    return min(x, y)
#################

#####ide_ele#####
ide_ele = 10**9 + 1
#################

class LazySegmentTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(l, r, x): 区間[l, r)をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        num: n以上の最小の2のべき乗
        data: 値配列(1-index)
        lazy: 遅延配列(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.data = [ide_ele] * 2 * self.num
        self.lazy = [None] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.data[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])

    def gindex(self, l, r):
            """
            伝搬する対象の区間を求める
            lm: 伝搬する必要のある最大の左閉区間
            rm: 伝搬する必要のある最大の右開区間
            """
            l += self.num
            r += self.num
            lm = l >> (l & -l).bit_length()
            rm = r >> (r & -r).bit_length()
            if l == r:
                l >>= 1
            while r > l:
                if l <= lm:
                    yield l
                if r <= rm:
                    yield r
                r >>= 1
                l >>= 1
            while l:
                yield l
                l >>= 1

    def propagates(self, *ids):
        """
        遅延伝搬処理
        ids: 伝搬する対象の区間 
        """
        for i in reversed(ids):
            v = self.lazy[i]
            if v is None:
                continue
            self.lazy[2 * i] = v
            self.lazy[2 * i + 1] = v
            self.data[2 * i] = v
            self.data[2 * i + 1] = v
            self.lazy[i] = None

    def update(self, l, r, x):
        """
        区間[l, r)の値をxに更新
        l, r: index(0-index)
        x: update value
        """
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                self.lazy[l] = x
                self.data[l] = x
                l += 1
            if r & 1:
                self.lazy[r - 1] = x
                self.data[r - 1] = x
            r >>= 1
            l >>= 1
        for i in ids:
            self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])


    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        *ids, = self.gindex(l, r)
        self.propagates(*ids)

        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.data[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.data[r - 1])
            l >>= 1
            r >>= 1
        return res

n, q = map(int, input().split())
stx = []
for _ in range(n):
    s, t, x = map(int, input().split())
    stx.append([x, s - x, t - x])
stx.sort(reverse=True)
d = [int(input()) for _ in range(q)]

import bisect

seg = LazySegmentTree([ide_ele]*q, segfunc, ide_ele)

for x, start, last in stx:
    l = bisect.bisect_left(d, start)
    r = bisect.bisect_left(d, last)
    seg.update(l, r, x)

for i, j in enumerate(d):
    res = seg.query(i, i + 1)
    if res == ide_ele:
        print(-1)
    else:
        print(res)

Submission status: Time Limit Exceeded

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

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 = list() # 工事中
    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 not working else working[0])
    return
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

    from heapq import heappush, heappop 

    running = []
    events = []
    delete = 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])
            delete.discard(temp[1])
        elif temp[-1] == 0:
            delete.add(temp[1])
        else:
            flag = 1
            while running:
                p = heappop(running)
                if p not in delete:
                    flag = 0
                    heappush(running, p)
                    print(p)
                    break
            if flag:
                print(-1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    from heapq import heappush, heappop 

    running = []
    events = []
    delete = set()

    n, q = map(int, input().split())
    for _ in range(n):
        s, t, x = map(int, input().split())
        time = max(s - x, 0)
        if t - x < 0:
            continue
        events.append((s - x, x, 1)) # 追加イベント
        events.append((t - x, x, 0)) # 削除イベント
    events.sort()
    ans = []
    idx = -1
    for _ in range(q):
        d = int(input())
        if d >= events[-1][0]:
            print(-1)
            continue
        while events[idx + 1][0] <= d:
            idx += 1
            if events[idx][2] == 1:
                heappush(running, events[idx][1])
                delete.discard(events[idx][1])
            else:
                delete.add(events[idx][1])
        flag = 1
        while running:
            x = heappop(running)
            if x not in delete:
                heappush(running, x)
                print(x)
                flag = 0
                break
        if flag:
            print(-1)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) # xで止まらなくなる
  task.append((s-x,1,x)) # xで止まる

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapで最小値を先頭に保つ

# 小さい時刻から順に見ていく
for a,b,c in task:
  if not b: # b == 0
    se.remove(c)
  elif b&1: # b == 1
    se.add(c)
    heappush(se_hp,c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

from heapq import heappush, heappop 

running = []
events = []
delete = set()

n, q = map(int, input().split())
for _ in range(n):
    s, t, x = map(int, input().split())
    time = max(s - x, 0)
    if t - x < 0:
        continue
    events.append((s - x, x, 1)) # 追加イベント
    events.append((t - x, x, 0)) # 削除イベント
events.sort()
ans = []
idx = -1
for _ in range(q):
    d = int(input())
    if d >= events[-1][0]:
        print(-1)
        #ans.append(-1)
        continue
    while events[idx + 1][0] <= d:
        idx += 1
        if events[idx][2] == 1:
            heappush(running, events[idx][1])
            delete.discard(events[idx][1])
        else:
            delete.add(events[idx][1])
    flag = 1
    while running:
        x = heappop(running)
        if x not in delete:
            heappush(running, x)
            print(x)
            #ans.append(x)
            flag = 0
            break
    if flag:
        print(-1)
        #ans.append(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()

from heapq import heappush, heappop 

running = []
events = []
delete = set()

n, q = map(int, input().split())
for _ in range(n):
    s, t, x = map(int, input().split())
    time = max(s - x, 0)
    if t - x < 0:
        continue
    events.append((s - x, x, 1)) # 追加イベント
    events.append((t - x, x, 0)) # 削除イベント
events.sort()
ans = []
idx = -1
for _ in range(q):
    d = int(input())
    if d >= events[-1][0]:
        ans.append(-1)
        continue
    while events[idx + 1][0] <= d:
        idx += 1
        if events[idx][2] == 1:
            heappush(running, events[idx][1])
            delete.discard(events[idx][1])
        else:
            delete.add(events[idx][1])
    flag = 1
    while running:
        x = heappop(running)
        if x not in delete:
            heappush(running, x)
            ans.append(x)
            flag = 0
            break
    if flag:
        ans.append(-1)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

input = sys.stdin.readline

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


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


def read_str_n():
    return list(map(str, input().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):
    E = []
    for i, (s, t, x) in enumerate(STX):
        E.append((s-x, 1, x, i))
        E.append((t-x, -1, x, i))
    E.sort(reverse=True)

    q = []
    done = set()
    ans = [-1] * Q
    for j, d in enumerate(D):
        while E and E[-1][0] <= d:
            t, e, x, i = E.pop()
            if e == 1:
                heapq.heappush(q, (x, i))
            else:
                done.add((x, i))

        while q and q[0] in done:
            done.remove(heapq.heappop(q))

        if q:
            ans[j] = q[0][0]

    for i in range(Q):
        print(ans[i])


def main():
    N, Q = read_int_n()
    STX = list(read_int_n() for _ in range(N))
    D = list(read_int() for _ in range(Q))
    (slv(N, Q, STX, D))


if __name__ == '__main__':
    main()

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
    from collections import Counter
    aq = [[s-x, x] for s, _, x in STX]
    rq = [[t-x, x] for _, t, x in STX]
    aq.sort(reverse=True)
    rq.sort(reverse=True)
    q = []
    ans = [-1] * Q
    done = Counter()
    for i, d in enumerate(D):
        while aq and aq[-1][0] <= d:
            _, x = aq.pop()
            heappush(q, x)
        while rq and rq[-1][0] <= d:
            _, x = rq.pop()
            done[x] += 1
        while q and q[0] in done:
            x = heappop(q)
            done[x] -= 1
            if done[x] == 0:
                done.pop(x)
        if q:
            ans[i] = q[0]
    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:
# -*- 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
    from collections import Counter
    aq = [[s-x, x] for s, _, x in STX]
    rq = [[t-x, x] for _, t, x in STX]
    aq.sort(reverse=True)
    rq.sort(reverse=True)
    q = []
    ans = []
    done = Counter()
    for d in D:
        while aq and aq[-1][0] <= d:
            _, x = aq.pop()
            heappush(q, x)
        while rq and rq[-1][0] <= d:
            _, x = rq.pop()
            done[x] += 1
        while q and q[0] in done:
            x = heappop(q)
            done[x] -= 1
            if done[x] == 0:
                done.pop(x)
        if q:
            ans.append(q[0])
        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:
# -*- 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
    from collections import Counter
    aq = [[s-x, x] for s, _, x in STX]
    rq = [[t-x, x] for _, t, x in STX]
    aq.sort(reverse=True)
    rq.sort(reverse=True)
    q = []
    ans = []
    done = Counter()
    for d in D:
        while aq and aq[-1][0] <= d:
            _, x = aq.pop()
            heappush(q, x)
        while rq and rq[-1][0] <= d:
            _, x = rq.pop()
            done[x] += 1
        while q and q[0] in done and done[q[0]] > 0:
            x = heappop(q)
            done[x] -= 1
            if done[x] == 0:
                done.pop(x)
        if q:
            ans.append(q[0])
        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:
# -*- 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
    from collections import Counter
    aq = [[s-x, x] for s, _, x in STX]
    rq = [[t-x, x] for _, t, x in STX]
    aq.sort(reverse=True)
    rq.sort(reverse=True)
    q = []
    ans = []
    done = Counter()
    for d in D:
        while aq and aq[-1][0] <= d:
            _, x = aq.pop()
            heappush(q, x)
        while rq and rq[-1][0] <= d:
            _, x = rq.pop()
            done[x] += 1
        while q and q[0] in done and done[q[0]] > 0:
            x = heappop(q)
            done[x] -= 1
        if q:
            ans.append(q[0])
        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()