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
input = sys.stdin.readline

def main():

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

    V = []

    for i in range(n):
        s, t, x = map(int, input().split())
        V.append((s-x, x, 1)) #1: insert
        V.append((t-x, x, 0)) #0: delete

    D = []
    for i in range(q):
        d = int(input())
        V.append((d, i, 2)) #2: query

    V.sort(key=lambda x:(x[0], x[2]))
    se = set()
    hq = []
    import heapq
    heapq.heapify(hq)
    ans = [-1]*q
    for t, v, p in V:
        if p == 1:
            se.add(v)
            heapq.heappush(hq, v)
        elif p == 0:
            se.remove(v)
        else:
            while hq and hq[0] not in se:
                heapq.heappop(hq)
            if hq:
                ans[v] = hq[0]

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():

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

    V = []

    for i in range(n):
        s, t, x = map(int, input().split())
        V.append((s-x, x, 1)) #1: insert
        V.append((t-x, x, 0)) #0: delete

    D = []
    for i in range(q):
        d = int(input())
        V.append((d, i, 2)) #2: query

    V.sort(key=lambda x:(x[0], x[2]))
    se = set()
    hq = []
    import heapq
    heapq.heapify(hq)
    ans = [-1]*q
    for t, v, p in V:
        if p == 1:
            se.add(v)
            heapq.heappush(hq, v)
        elif p == 0:
            se.discard(v)
        else:
            while hq and hq[0] not in se:
                heapq.heappop(hq)
            if hq:
                ans[v] = hq[0]

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():

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

    T = []
    X = [[0, 0, 0] for _ in range(n)]
    for i in range(n):
        s, t, x = map(int, input().split())
        T.append(s-x)
        T.append(t-x)
        X[i][0], X[i][1], X[i][2] = x, s-x, t-x

    X.sort(reverse=True)

    D = [0]*q
    for i in range(q):
        d = int(input())
        T.append(d)
        D[i] = d

    toid = {}
    T = list(set(T))
    T.sort()
    for i, t in enumerate(T):
        toid[t] = i

    m = len(T)
    # identity element
    ide_ele = 10**18

    A = [ide_ele]*m

    # num: n以上の最小の2のべき乗
    num = 2**(m-1).bit_length()
    seg = [ide_ele]*2*num
    lazy = [None]*2*num

    def segfunc(x, y):
        if x >= y:
            return y
        else:
            return x

    def init(init_val):
        # set_val
        for i in range(m):
            seg[i+num-1] = init_val[i]
        # built
        for i in range(num-2, -1, -1):
            seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

    # 伝搬する区間のids(1-indexed)を全て列挙する
    # 降順で列挙される
    def gindex(p, q):
        p += num
        q += num
        # 1-indexedにしたとき、2*k > kの区間は更新する区間に含まれる
        # (p & -p)で最後の1bitを求めて、それで割ってからシフト
        pm = (p // (p & -p)) >> 1
        qm = (q // (q & -q)) >> 1
        while p < q:
            if q <= qm:
                yield q
            if p <= pm:
                yield p
            p = p >> 1
            q = q >> 1
        while p:
            yield p
            p = p >> 1

    # 1-indexedで降順のidを渡す
    def propagate(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if v is None:
                continue
            lazy[2*i-1] = seg[2*i-1] = lazy[2*i] = seg[2*i] = v
            lazy[i-1] = None

    def update(p, q, x):
        *ids, = gindex(p, q)
        # 1. topdwon
        propagate(*ids)

        # 2. update
        p += num - 1
        q += num - 2
        while q-p > 1:
            if p&1 == 0: #左のnode: == 1, 右のnode: == 0
                lazy[p] = seg[p] = x
            if q&1 == 1: #左のnode: == 1, 右のnode: == 0
                lazy[q] = seg[q] = x
                q -= 1 # 隣に移動
            p = p//2 # 隣のnodeの親にアクセス
            q = (q-1)//2 #親のnodeにアクセス
        if p == q:
            lazy[p] = seg[p] = x
        else:
            if (p-1)//2 == (q-1)//2:
                p = (p-1)//2
                lazy[p] = seg[p] = x
            else:
                lazy[p] = seg[p] = x
                lazy[q] = seg[q] = x

        # 3. bottom up
        for i in ids:
            seg[i-1] = segfunc(seg[2*i-1], seg[2*i])

    def query(p, q):
        if q <= p:
            return ide_ele

        # 1. topdwon
        #*ids, = gindex(p, q)
        propagate(*gindex(p, q))

        # 2. 区間[p, q)で取得
        p += num - 1
        q += num - 2
        res = ide_ele
        while q-p>1:
            if p&1 == 0: #左のnode: == 1, 右のnode: == 0
                res = segfunc(res, seg[p])
            if q&1 == 1: #左のnode: == 1, 右のnode: == 0
                res = segfunc(res, seg[q])
                q -= 1 # 隣に移動
            p = p//2 # 隣のnodeの親にアクセス
            q = (q-1)//2 #親のnodeにアクセス
        if p == q:
            res = segfunc(res, seg[p])
        else:
            if (p-1)//2 == (q-1)//2:
                p = (p-1)//2
                res = segfunc(res, seg[p])
            else:
                res = segfunc(segfunc(res, seg[p]), seg[q])
        #print(p, q)
        return res

    init(A)

    for x, s, t in X:
        s = toid[s]
        t = toid[t]
        update(s, t, x)

    for d in D:
        d = toid[d]
        ans = query(d, d+1)
        if ans == ide_ele:
            print(-1)
        else:
            print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():

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

    T = []
    X = [[0, 0, 0] for _ in range(n)]
    for i in range(n):
        s, t, x = map(int, input().split())
        T.append(s-x)
        T.append(t-x)
        X[i][0], X[i][1], X[i][2] = x, s-x, t-x

    X.sort(reverse=True)

    D = [0]*q
    for i in range(q):
        d = int(input())
        T.append(d)
        D[i] = d

    toid = {}
    T = list(set(T))
    T.sort()
    import bisect
    for t in T:
        id = bisect.bisect_left(T, t)
        toid[t] = id

    m = len(T)
    # identity element
    ide_ele = 10**18

    A = [ide_ele]*m

    # num: n以上の最小の2のべき乗
    num = 2**(m-1).bit_length()
    seg = [ide_ele]*2*num
    lazy = [None]*2*num

    def segfunc(x, y):
        if x >= y:
            return y
        else:
            return x

    def init(init_val):
        # set_val
        for i in range(m):
            seg[i+num-1] = init_val[i]
        # built
        for i in range(num-2, -1, -1):
            seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

    # 伝搬する区間のids(1-indexed)を全て列挙する
    # 降順で列挙される
    def gindex(p, q):
        p += num
        q += num
        # 1-indexedにしたとき、2*k > kの区間は更新する区間に含まれる
        # (p & -p)で最後の1bitを求めて、それで割ってからシフト
        pm = (p // (p & -p)) >> 1
        qm = (q // (q & -q)) >> 1
        while p < q:
            if q <= qm:
                yield q
            if p <= pm:
                yield p
            p = p >> 1
            q = q >> 1
        while p:
            yield p
            p = p >> 1

    # 1-indexedで降順のidを渡す
    def propagate(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if v is None:
                continue
            lazy[2*i-1] = seg[2*i-1] = lazy[2*i] = seg[2*i] = v
            lazy[i-1] = None

    def update(p, q, x):
        *ids, = gindex(p, q)
        # 1. topdwon
        propagate(*ids)

        # 2. update
        p += num - 1
        q += num - 2
        while q-p > 1:
            if p&1 == 0: #左のnode: == 1, 右のnode: == 0
                lazy[p] = seg[p] = x
            if q&1 == 1: #左のnode: == 1, 右のnode: == 0
                lazy[q] = seg[q] = x
                q -= 1 # 隣に移動
            p = p//2 # 隣のnodeの親にアクセス
            q = (q-1)//2 #親のnodeにアクセス
        if p == q:
            lazy[p] = seg[p] = x
        else:
            if (p-1)//2 == (q-1)//2:
                p = (p-1)//2
                lazy[p] = seg[p] = x
            else:
                lazy[p] = seg[p] = x
                lazy[q] = seg[q] = x

        # 3. bottom up
        for i in ids:
            seg[i-1] = segfunc(seg[2*i-1], seg[2*i])

    def query(p, q):
        if q <= p:
            return ide_ele

        # 1. topdwon
        #*ids, = gindex(p, q)
        propagate(*gindex(p, q))

        # 2. 区間[p, q)で取得
        p += num - 1
        q += num - 2
        res = ide_ele
        while q-p>1:
            if p&1 == 0: #左のnode: == 1, 右のnode: == 0
                res = segfunc(res, seg[p])
            if q&1 == 1: #左のnode: == 1, 右のnode: == 0
                res = segfunc(res, seg[q])
                q -= 1 # 隣に移動
            p = p//2 # 隣のnodeの親にアクセス
            q = (q-1)//2 #親のnodeにアクセス
        if p == q:
            res = segfunc(res, seg[p])
        else:
            if (p-1)//2 == (q-1)//2:
                p = (p-1)//2
                res = segfunc(res, seg[p])
            else:
                res = segfunc(segfunc(res, seg[p]), seg[q])
        #print(p, q)
        return res

    init(A)

    for x, s, t in X:
        s = toid[s]
        t = toid[t]
        update(s, t, x)

    for d in D:
        d = toid[d]
        ans = query(d, d+1)
        if ans == ide_ele:
            print(-1)
        else:
            print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():

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

    def segfunc(x, y):
        if x >= y:
            return y
        else:
            return x

    def init(init_val):
        # set_val
        for i in range(n):
            seg[i+num-1] = init_val[i]
        # built
        for i in range(num-2, -1, -1):
            seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

    # 伝搬する区間のids(1-indexed)を全て列挙する
    # 降順で列挙される
    def gindex(p, q):
        p += num
        q += num
        # 1-indexedにしたとき、2*k > kの区間は更新する区間に含まれる
        # (p & -p)で最後の1bitを求めて、それで割ってからシフト
        pm = (p // (p & -p)) >> 1
        qm = (q // (q & -q)) >> 1
        while p < q:
            if q <= qm:
                yield q
            if p <= pm:
                yield p
            p = p >> 1
            q = q >> 1
        while p:
            yield p
            p = p >> 1

    # 1-indexedで降順のidを渡す
    def propagate(*ids):
        for i in reversed(ids):
            v = lazy[i-1]
            if v is None:
                continue
            lazy[2*i-1] = seg[2*i-1] = lazy[2*i] = seg[2*i] = v
            lazy[i-1] = None

    def update(p, q, x):
        *ids, = gindex(p, q)
        # 1. topdwon
        propagate(*ids)

        # 2. update
        p += num - 1
        q += num - 2
        while q-p > 1:
            if p&1 == 0: #左のnode: == 1, 右のnode: == 0
                lazy[p] = seg[p] = x
            if q&1 == 1: #左のnode: == 1, 右のnode: == 0
                lazy[q] = seg[q] = x
                q -= 1 # 隣に移動
            p = p//2 # 隣のnodeの親にアクセス
            q = (q-1)//2 #親のnodeにアクセス
        if p == q:
            lazy[p] = seg[p] = x
        else:
            if (p-1)//2 == (q-1)//2:
                p = (p-1)//2
                lazy[p] = seg[p] = x
            else:
                lazy[p] = seg[p] = x
                lazy[q] = seg[q] = x

        # 3. bottom up
        for i in ids:
            seg[i-1] = segfunc(seg[2*i-1], seg[2*i])

    def query(p, q):
        if q <= p:
            return ide_ele

        # 1. topdwon
        #*ids, = gindex(p, q)
        propagate(*gindex(p, q))

        # 2. 区間[p, q)で取得
        p += num - 1
        q += num - 2
        res = ide_ele
        while q-p>1:
            if p&1 == 0: #左のnode: == 1, 右のnode: == 0
                res = segfunc(res, seg[p])
            if q&1 == 1: #左のnode: == 1, 右のnode: == 0
                res = segfunc(res, seg[q])
                q -= 1 # 隣に移動
            p = p//2 # 隣のnodeの親にアクセス
            q = (q-1)//2 #親のnodeにアクセス
        if p == q:
            res = segfunc(res, seg[p])
        else:
            if (p-1)//2 == (q-1)//2:
                p = (p-1)//2
                res = segfunc(res, seg[p])
            else:
                res = segfunc(segfunc(res, seg[p]), seg[q])
        #print(p, q)
        return res

    T = []
    X = [[0, 0, 0] for _ in range(n)]
    for i in range(n):
        s, t, x = map(int, input().split())
        T.append(s-x)
        T.append(t-x)
        X[i][0], X[i][1], X[i][2] = x, s-x, t-x

    X.sort(reverse=True)

    D = [0]*q
    for i in range(q):
        d = int(input())
        T.append(d)
        D[i] = d

    toid = {}
    T = list(set(T))
    T.sort()
    import bisect
    for t in T:
        id = bisect.bisect_left(T, t)
        toid[t] = id

    m = len(T)
    # identity element
    ide_ele = 10**18

    A = [ide_ele]*m

    # num: n以上の最小の2のべき乗
    num = 2**(m-1).bit_length()
    seg = [ide_ele]*2*num
    lazy = [None]*2*num

    init(A)

    for x, s, t in X:
        s = toid[s]
        t = toid[t]
        update(s, t, x)

    for d in D:
        d = toid[d]
        ans = query(d, d+1)
        if ans == ide_ele:
            print(-1)
        else:
            print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
stx=[list(map(int,input().split()))[::-1] for i in range(n)]
stx=sorted(stx)
d=[int(input()) for i in range(q)]
ans=[-1]*q
safe=[1]*q

for i in range(n):
  s=stx[i][2]-stx[i][0]
  t=stx[i][1]-stx[i][0]
  for j in range(q):
    if safe[j]==1 and s<=d[j] and d[j]<t:
      safe[j]=0
      ans[j]=stx[i][0]
for j in range(q):
  print(ans[j])

Submission status: Time Limit Exceeded

Solution code:
import sys;input=sys.stdin.readline
N, Q = map(int, input().split())
X = []
for _ in range(N):
    s, t, x = map(int, input().split())
    X.append((2*s-2*x-1, 0, x))
    X.append((2*t-2*x-1, 1, x))

inf = 10**18
X.append((-inf, 0, inf))
X.append((inf, 1, inf))

X.sort(key=lambda x: x[0])

from heapq import *
from collections import defaultdict
#print(X[1:-1])
j = 0
ll = []
vs = set()
d = defaultdict(int)
for _ in range(Q):
    q = int(input())
    while 1:
        u, f, x = X[j]
        if u > 2*q:
            break
        if f:
            d[x] += 1
        else:
            heappush(ll, x)
        j += 1
    while 1:
        x = heappop(ll)
        if d[x] > 0:
            d[x] -= 1
            continue
        heappush(ll, x)
        if x == inf:
            print(-1)
        else:
            print(x)
        break

Submission status: Time Limit Exceeded

Solution code:
import sys;input=sys.stdin.readline
N, Q = map(int, input().split())
X = []
for _ in range(N):
    s, t, x = map(int, input().split())
    X.append((2*s-2*x-1, 0, x))
    X.append((2*t-2*x-1, 1, x))

inf = 10**18
X.append((-inf, 0, inf))
X.append((inf, 1, inf))

X.sort(key=lambda x: x[0])

from heapq import *
from collections import defaultdict
#print(X[1:-1])
j = 0
ll = []
vs = set()
d = defaultdict(int)
for _ in range(Q):
    q = int(input())
    while X[j][0] < 2*q:
#        print(X[j])
        _, f, x = X[j]
        if f:
            d[x] += 1
        else:
            heappush(ll, x)
        j += 1
#    print(ll, j)
#    print(d, ll)
#    j -= 1
    while 1:
        x = heappop(ll)
        if d[x] > 0:
            d[x] -= 1
            continue
        heappush(ll, x)
        if x == inf:
            print(-1)
        else:
            print(x)
        break

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n, q = map(int, input().split())
    s = [0] * n
    t = [0] * n
    x = [0] * n
    koji = [[0 for i in range(3)] for j in range(n)]
    for i in range(n):
        s[i], t[i], x[i] = map(int, input().split())
        koji[i][0] = x[i]
        koji[i][1]=s[i]-x[i]
        koji[i][2]=t[i]-x[i]
    koji.sort()
    d = [int(input()) for _ in range(q)]
    for i in range(q):
        for j in range(n):
            if d[i]>=koji[j][1] and d[i]<koji[j][2]:
                print(koji[j][0])
                break
            elif j==n-1:
                print(-1)
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from heapq import heappop,heappush
input = sys.stdin.readline
n,Q = map(int,input().split())
stx = [list(map(int,input().split())) for i in range(n)]
dls = [int(input()) for i in range(Q)]
event = []
for i in range(n):
  s,t,x = stx[i]
  event.append((s-x,1,x))
  event.append((t-x,-1,x))
for i in range(Q):
  d = dls[i]
  event.append((d,2,i))
event.sort()
ans = [-1]*Q
s = set()
hq = []
for t,q,x in event:
  if q == 1:
    s.add(x)
    heappush(hq,x)
  elif q == -1:
    s.remove(x)
  elif q == 2:
    while hq and hq[0] not in s:
      heappop(hq)
    if hq:
      ans[x] = hq[0]
    else:
      ans[x] = -1
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc128/tasks/abc128_es

それぞれの工事がどのDの範囲の人を制限するのか計算すればよい
Xiが最も小さいものが影響を及ぼす。
heap & いもす法で解ける？

具体的には、

X-S <= D < X-T　のDが封鎖を食らう
"""
import heapq
N,Q = map(int,input().split())

sti = []
goi = []
STX = []

for i in range(N):

    S,T,X = map(int,input().split())
    sti.append([S-X,i])
    goi.append([T-X,i])

    STX.append([S,T,X])

sti.sort()
goi.sort()
sti.append([float("inf"),0])
goi.append([float("inf"),0])

D = []
ans = [-1] * Q
for i in range(Q):

    d = int(input())
    D.append(d)
D.append(float("inf"))

si = 0
gi = 0
di = 0

hq = []
inlis = [False] * N

while di != Q and gi != N:

    #print (si,gi,di)

    st,stind = sti[si]
    startX = STX[stind][2]
    go,goind = goi[gi]
    nd = D[di]

    if min(st,go,nd) == go:
        inlis[goind] = False
        gi += 1
        
    elif min(st,go,nd) == st:
        inlis[stind] = True
        heapq.heappush( hq , [startX,stind])
        si += 1
        
    else:

        while len(hq) > 0 and not inlis[hq[0][1]]:
            heapq.heappop(hq)

        if len(hq) == 0:
            ans[di] = -1
        else:
            ans[di] = hq[0][0]
        di += 1
        

    #print (hq)
print ("\n".join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
def main():
    from heapq import heappush, heappop
    import sys
    sys.setrecursionlimit(10 ** 7)
    
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines

    n,q=map(int,readline().split())
    stx = [[int(x) for x in readline().split()] for _ in range(n)]
    event=[]
    stop=set()
    for s,t,x in stx:
        event.append([s-x,1,x])
        event.append([t-x,-1,x])
    for i in range(q):
        event.append([int(input()),2,i])
    event.sort()
    
    ans=[0]*q
    
    stop=set()
    hq=[]
    for e in event:
        t,op,x=map(lambda x:x,e)
        if op==1:
            heappush(hq,x)
            stop.add(x)
        elif op==-1:
            stop.remove(x)
    
        else:
            while hq and hq[0] not in stop:
                heappop(hq) 
            ans[x]=hq[0] if hq else -1
        
    for x in ans:
        print(x)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from heapq import heappush, heappop
    import sys
    sys.setrecursionlimit(10 ** 7)
    
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines

    n,q=map(int,readline().split())
    stx = [[int(x) for x in readline().split()] for _ in range(n)]
    event=[]
    stop=set()
    for s,t,x in stx:
        event.append([s-x,1,x])
        event.append([t-x,-1,x])
    event.sort()
    d=[int(readline()) for _ in range(q)]

    k=0
    for i in range(q):
        while k<2*n and event[k][0]<=d[i]:
            if event[k][1]==1: stop.add(event[k][2])
            else: stop.remove(event[k][2])
            k+=1
        print(min(stop) if stop!=set() else -1)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(10 ** 7)
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,q=map(int,readline().split())
stx = [[int(x) for x in readline().split()] for _ in range(n)]
event=[]
stop=set()
for s,t,x in stx:
    event.append([s-x,1,x])
    event.append([t-x,-1,x])
event.sort()
d=[int(readline()) for _ in range(q)]

k=0
for i in range(q):
    while k<2*n and event[k][0]<=d[i]:
        if event[k][1]==1: stop.add(event[k][2])
        else: stop.remove(event[k][2])
        k+=1
    print(min(stop) if stop!=set() else -1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(10 ** 7)

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

event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x,1,x))
    event.append((t-x,-1,x))

for i in range(q):
    event.append((int(input()),2,i))
event.sort()

ans=[0]*q

stop=set()
hq=[]
for t,op,x in event:
    if op==1:
        heappush(hq,x)
        stop.add(x)
    elif op==-1:
        stop.remove(x)

    else:
        while hq and hq[0] not in stop:
            heappop(hq) 
        ans[x]=hq[0] if hq else -1
    
for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import heapq
import sys
sys.setrecursionlimit(10 ** 7)

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

event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x,1,x))
    event.append((t-x,-1,x))

for i in range(q):
    event.append((int(input()),2,i))
event.sort()

ans=[0]*q

stop=set()
hq=[]
for t,op,x in event:
    if op==1:
        heappush(hq,x)
        stop.add(x)
    elif op==-1:
        stop.remove(x)

    else:
        while hq and hq[0] not in stop:
            heappop(hq) 
        ans[x]=hq[0] if hq else -1
    
for x in ans:
    print(x)

Submission status: Time Limit Exceeded

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

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

event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x,1,x))
    event.append((t-x,-1,x))

for i in range(q):
    event.append((int(input()),2,i))
event.sort()

ans=[0]*q

stop=set()
hq=[]
for t,op,x in event:
    if op==1:
        heapq.heappush(hq,x)
        stop.add(x)
    elif op==-1:
        stop.remove(x)

    else:
        while hq and hq[0] not in stop:
            heapq.heappop(hq) 
        ans[x]=hq[0] if hq else -1
    
for x in ans:
    print(x)

Submission status: Time Limit Exceeded

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

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

event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append([s-x,1,x])
    event.append([t-x,-1,x])

for i in range(q):
    event.append([int(input()),2,i])
event.sort()

ans=[0]*q

stop=set()
hq=[]
for e in event:
    t,op,x=map(lambda x:x,e)
    if op==1:
        heapq.heappush(hq,x)
        stop.add(x)
    elif op==-1:
        stop.remove(x)

    else:
        while hq and hq[0] not in stop:
            heapq.heappop(hq) 
        ans[x]=hq[0] if hq else -1
    
for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,q=map(int,input().split())

event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append([s-x,1,x])
    event.append([t-x,-1,x])

for i in range(q):
    event.append([int(input()),2,i])
event.sort()

ans=[0]*q

stop=set()
hq=[]
for e in event:
    t,op,x=map(lambda x:x,e)
    if op==1:
        heapq.heappush(hq,x)
        stop.add(x)
    elif op==-1:
        stop.remove(x)

    else:
        while hq and hq[0] not in stop:
            heapq.heappop(hq) 
        ans[x]=hq[0] if hq else -1
    
for x in ans:
    print(x)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,q=map(int,input().split())

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

k=0
stop=set()
hq=[]
for i in range(q):
    while k<2*n and event[k][0]<=d[i]:
        x=event[k][2]
        if event[k][1]==1:
            heapq.heappush(hq,x)
            stop.add(x)
        else:
            stop.remove(x)
        k+=1
    while hq and hq[0] not in stop:
        heapq.heappop(hq) 
    print(hq[0] if hq else -1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n,q=map(int,input().split())

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

k=0
stop=set()
hq=[]
for i in range(q):
    while k<2*n and event[k][0]<=d[i]:
        x=event[k][2]
        if event[k][1]==1:
            heapq.heappush(hq,x)
            stop.add(x)
        else:
            stop.remove(x)
        k+=1
    while hq and hq[0] not in stop:
        heapq.heappop(hq) 
    print(hq[0] if hq!=[] else -1)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
event=[]

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

k=0
stop={}
for i in range(q):
    while k<2*n and event[k][0]<=d[i]:
        if event[k][1]==1: stop[event[k][2]]=1
        else: stop.pop(event[k][2])
        k+=1
    print(min(stop) if stop!={} else -1)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,q=map(int,input().split())

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

k=0
stop=[]
for i in range(q):
    while k<2*n and event[k][0]<=d[i]:
        if event[k][1]==1: bisect.insort(stop,event[k][2])
        else: stop.remove(event[k][2])
        k+=1
    print(stop[0] if stop!=[] else -1)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
event=[]
stop=set()
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append([s-x,1,x])
    event.append([t-x,-1,x])
event.sort()
d=[int(input()) for _ in range(q)]

k=0
for i in range(q):
    while k<2*n and event[k][0]<=d[i]:
        if event[k][1]==1: stop.add(event[k][2])
        else: stop.remove(event[k][2])
        k+=1
    print(min(stop) if stop!=set() else -1)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

n, q = map(int, input().split())
stx = [list(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

INF = 10 ** 9 + 1

li = []
for s, t, x in stx:
    li.append([s - x, 1, x])
    li.append([t - x, -1, x])

li.sort()
x_st = set([INF])
xxs = []
xs = [INF]

i = 0
for xx, check, x in li:
    if check == -1:
        x_st.remove(x)
    else:
        x_st.add(x)

    xxs.append(xx)
    xs.append(min(x_st))

for e in d:
    i = bisect_right(xxs, e)
    ans = xs[i]
    if ans == INF:
        ans = -1
    print(ans)