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

Solution code:
import sys
from bisect import bisect_left
def input(): return sys.stdin.readline().strip()

def main():
    """
    計算量の落とし方が全くわからんので以下のコードを参考に写経。。。
    https://atcoder.jp/contests/abc128/submissions/7712981
    """
    N, Q = map(int, input().split())
    work = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        work.append((x, s - x, t - x))
    work.sort(key=lambda x: (x[0], x[1]))
    start = [int(input()) for _ in range(Q)]

    """
    工事箇所を原点にスライドさせる事で考察を易化しておく。
    各工事(x, s, t)に対して（既にs, tは原点への移動を考慮済み）s<=d<tなるdの個数を求めたい
    startは既に昇順に並んでいるので二分探索でs<=d_i<d_{i+1}<...<d_{j-1}<tなるi=left, j=rightを求める。

    そのあと[left, right)をxで埋めていくが、愚直に(right-left)回xを代入していくとO(Q)かかってTLEするので
    skip[left]=(以前に[left, right)を埋めたときのright)を格納しておく。
    これによりansの表を毎度全走査しなくてもよくなり書き込み範囲のオーバーラップがだいぶ削減される。

    しかしskipを使っても飛んだ先がまたskip命令入ってる可能性もあるから、AC出来るのはやや偶然感あり。。。
    """

    ans = [-1] * Q
    skip = [-1] * Q
    for x, s, t in work:
        left = bisect_left(start, s)
        right = bisect_left(start, t)
        while left < right:
            if skip[left] == -1:
                ans[left] = x
                skip[left] = right
                left += 1
            else:
                left = skip[left]

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




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left as b;n,q=map(int,input().split());w=sorted([list(map(int,input().split()))[::-1]for _ in[0]*n]);p=[int(input())for _ in[0]*q];a=[-1]*q;o=[-1]*q
for x,t,s in w:
  l,r=b(p,s-x),b(p,t-x)
  while l<r:
    if o[l]+1:l=o[l]
    else:a[l],o[l]=x,r;l+=1
print(*a)

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect_right
n,q=map(int,input().split())
w=[list(map(int,input().split()))[::-1]for _ in range(n)]
p=[int(input())for _ in range(q)]
w.sort()
ans=[-1]*q
to=[-1]*q
for x,t,s in w:
  l,r=bisect_left(p,s-x),bisect_left(p,t-x)
  while l<r:
    if to[l]==-1:
      ans[l]=x
      to[l]=r
      l+=1
    else:
      l=to[l]
print(*ans)

Submission status: Accepted

Solution code:
import heapq as hq
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

def main():
    n,q = nm()
    tl = []
    ins = list()
    dlt = list()
    vv = [tuple(nm()) for _ in range(n)]
    tl = [(s-x, 1, x) for s, _, x in vv]
    tl.extend([(t-x, 0, x) for _, t, x in vv])
    ww = [ni() for _ in range(q)]
    tl.extend([(t, 2) for t in ww])
    tl.sort()

    for x in tl:
        if x[1] == 1:
            hq.heappush(ins, x[2])
        elif x[1] == 0:
            hq.heappush(dlt, x[2])
            while dlt and ins[0] == dlt[0]:
                hq.heappop(ins)
                hq.heappop(dlt)
        else:
            print(-1 if not ins else ins[0])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

N,Q=map(int,input().split())
kouji=[]
for i in range(0,N):
    s,t,x=map(int,input().split())
    kouji.append([x,s,t])

d=[]
for i in range(0,Q):
    d.append(int(input()))

kouji.sort(reverse=True)

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

N0 = 2**(Q-1).bit_length()
data = [None]*(2*N0)
INF = (-1,-1)
# 区間[l, r+1)の値をvに書き換える
# vは(t, value)という値にする (新しい値ほどtは大きくなる)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
# a_iの現在の値を取得
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
# これを呼び出す
def query(k):
    return _query(k)[1]

time=0
for i in range(0,N):
    x,s,t=kouji[i]
    start=0
    end=Q-1
    while end-start>1:
        test=(end+start)//2
        if d[test]>=s-x:
            end=test
        else:
            start=test
    if d[start]>=s-x:
        l=start
    elif d[end]>=s-x:
        l=end
    else:
        l=Q

    start=0
    end=Q-1
    while end-start>1:
        test=(end+start)//2
        if t-x-1>=d[test]:
            start=test
        else:
            end=test
    if t-x-1>=d[end]:
        r=end
    elif t-x-1>=d[start]:
        r=start
    else:
        r=-1
    if r!=-1 and l!=Q and r>=l:
        update(l,r+1,(time,x))
    time+=1

for i in range(0,Q):
    print(query(i))

Submission status: Accepted

Solution code:
from collections import deque, defaultdict
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
events = [None] * (2*N)
for i in range(N):
    S, T, X = map(int, input().split())
    events[2*i] = (S-X, X)
    events[2*i+1] = (T-X, -X)
events.sort(key=lambda x: x[0])
events = deque(events)
ans = [0] * Q
cur = []
remove = defaultdict(int)
for i in range(Q):
    D = int(input())
    while events and events[0][0] <= D:
        t, x = events.popleft()
        if x > 0:
            heappush(cur, x)
        else:
            remove[-x] += 1
    while cur and remove[cur[0]]:
        remove[cur[0]] -= 1
        heappop(cur)
    ans[i] = cur[0] if cur else -1
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys

input = sys.stdin.buffer.readline


n, q = map(int, input().split())
STX = [list(map(int, input().split())) for _ in range(n)]
task = []
for s, t, x in STX:
    task.append((t - x, 0, x))
    task.append((s - x, 1, x))
for i in range(q):
    d = int(input())
    task.append((d, 2, i))

task.sort()
kouho = set()
kouho_hp = []
ans = [-1] * q
for a, b, c in task:
    if b == 0:
        kouho.remove(c)
    if b == 1:
        kouho.add(c)
        heappush(kouho_hp, c)
    if b == 2:
        while kouho_hp and kouho_hp[0] not in kouho:
            heappop(kouho_hp)
        if not kouho_hp:
            continue
        else:
            ans[c] = kouho_hp[0]
        # heapは0-indexが最小値になっているからheapified_list[0]でもよい
print(*ans, sep="\n")

Submission status: Accepted

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

n,q = map(int,input().split())
imos = []
for i in range(n):
    s,t,x = map(int,input().split())
    imos.append((s-x,x))
    imos.append((t-x,-x))
ans = set()
j = 0
for i in range(q):
    d = int(input())
    imos.append((d,1e100))
imos.sort()
m = 1e100
flag = False
for t,stop in imos:
    if stop == 1e100:
        if ans:
            if not flag:
                m = min(ans)
                flag = True
            print(m)
        else:
            print(-1)
    elif stop > 0:
        ans.add(stop)
        if stop < m:
            m = stop
            flag = True
    else:
        ans.remove(-stop)
        if m == -stop:flag = False

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc128/submissions/11722664

def main():
    from collections import deque, namedtuple
    from heapq import heappush, heappop
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Event = namedtuple('Event', 'pos start end')
    UC = namedtuple('UC', 'pos end')  # UnderConstruction

    N, Q = map(int, input().split())

    events = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        e = Event(pos=x, start=s - x, end=t - x)  # 時間[s-x,t-x)にpos=0にいるとpos=xで工事中
        events.append(e)
    events.sort(key=attrgetter('start'))
    events = deque(events)

    D = (int(input()) for _ in range(Q))

    ans = [-1] * Q
    h = []
    for idx, d in enumerate(D):
        while events and events[0].start <= d:
            e = events.popleft()
            heappush(h, UC(pos=e.pos, end=e.end))

        while h and h[0].end <= d:
            heappop(h)

        if h:
            ans[idx] = h[0].pos

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from bisect import bisect_left
    from collections import namedtuple
    from operator import attrgetter
    import sys

    input = sys.stdin.readline
    Event = namedtuple('Event', 'pos start end')

    N, Q = map(int, input().split())

    events = []
    for _ in range(N):
        s, t, x = map(int, input().split())
        e = Event(pos=x, start=s - x, end=t - x)  # 時間[s-x,t-x)にpos=0にいるとpos=xで工事中
        events.append(e)
    events.sort(key=attrgetter('pos'))

    D = [int(input()) for _ in range(Q)]

    ans = [-1] * Q
    see = [-1] * Q
    for e in events:
        left = bisect_left(D, e.start)
        right = bisect_left(D, e.end)
        # Dの要素で index が [left,right) 内のものは e.pos で工事中
        # e.pos 昇順ソートしているので, ans[idx] には工事中の最小のposが入る
        idx = left
        while idx < right:
            if ~ans[idx]:
                idx = see[idx]
                continue
            ans[idx] = e.pos
            see[idx] = right
            idx += 1
            
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
n, q = map(int, input().split())
STX = []
for i in range(n):
    s, t, x = map(int, input().split())
    STX.append((s, t, x))
STX.sort(key=lambda _: _[2])
S, T, X = [], [], []
for stx in STX:
    s, t, x = stx
    S.append(s)
    T.append(t)
    X.append(x)
D = [int(input()) for j in range(q)]
A = [-1 for j in range(q)]
B = [-1 for j in range(q)]
for i in range(n):
    l = bisect.bisect_left(D, S[i]-X[i])
    r = bisect.bisect_left(D, T[i]-X[i])
    while l < r:
        if B[l] == -1:
            A[l] = X[i]
            B[l] = r
            l += 1
        else:
            l = B[l]
print(*A, sep='\n')

Submission status: Accepted

Solution code:
def examA():
    def calc_L(x1,y1,x2,y2):
        return ((x2-x1)**2 + (y2-y1)**2)**0.5
    N = I()
    X = [LI()for _ in range(N)]
    ans = 0
    for x in itertools.permutations(X):
        cur = 0
        for i in range(1,N):
            cur += calc_L(x[i-1][0],x[i-1][1],x[i][0],x[i][1])
        #print(x,cur)
        ans += cur
    for i in range(1,N+1):
        ans /= i
    print(ans)
    return

def examB():
    def judge(n):
        sn = 0
        for i in n:
            sn += int(i)
        if int(n)%sn==0:
            return "Yes"
        return "No"
    N = SI()
    ans = judge(N)
    print(ans)
    return

def examC():
    N, K = LI()
    P = LI()
    ans = 0
    S = [0]*(N+1)
    for i in range(N):
        S[i+1] = S[i]+(P[i]+1)/2
    for i in range(N-K+1):
        cur = S[i+K] - S[i]
        if cur>ans:
            ans = cur
    print(ans)
    return

def examD():
    def bfs(n,V,s,W):
        visited = [False]*n
        que = deque()
        que.append(s)
        while(que):
            now = que.pop()
            visited[now] = True
            for ne in V[now]:
                if visited[ne]:
                    continue
                W[ne] += W[now]
                que.append(ne)
        return W
    N, Q = LI()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    W = [0] * N
    for _ in range(Q):
        p, x = LI()
        W[p-1] += x
    ans = bfs(N,V,0,W)
    print(" ".join(map(str,ans)))
    return

def examE():
    def bfs(n,edges,s):
        L = [inf]*n
        que = deque()
        que.append(s)
        L[s] = 0
        while(que):
            now = que.popleft()
            for ne in edges[now]:
                if L[ne]>L[now]+1:
                    L[ne] = L[now]+1
                    que.append(ne)
        return L
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    F = bfs(N,V,0)
    S = bfs(N,V,N-1)
    f = 0; s = 0
    for i in range(N):
        if F[i]>S[i]:
            s += 1
        else:
            f += 1
    if f>s:
        print("Fennec")
    else:
        print("Snuke")
    return

def examF():
    # 区間加算、上書き、一点取得
    class SegmentTree:
        def __init__(self, n, ele, segfun):
            #####単位元######要設定0or1orinf
            self.ide_ele = ele
            self.segfun = segfun
            ####################
            self.n = n
            self.N0 = 1 << n.bit_length()
            self.data = [self.ide_ele] * (self.N0 * 2)

        def update_add(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] += val
                    l += 1
                if r & 1:
                    self.data[r - 1] += val
                    r -= 1
                l //= 2
                r //= 2

        def update(self, l, r, val):
            l += self.N0
            r += self.N0
            while l < r:
                if l & 1:
                    self.data[l] = self.segfun(self.data[l], val)
                    l += 1
                if r & 1:
                    self.data[r - 1] = self.segfun(self.data[r - 1], val)
                    r -= 1
                l //= 2
                r //= 2

        def query(self, i):
            i += len(self.data) // 2
            ret = self.data[i]
            while i > 0:
                i //= 2
                ret = self.segfun(ret, self.data[i])
            return ret

    N, Q = LI()
    X = []
    for _ in range(N):
        s,t,x = LI()
        l = max(0,s-x)
        r = t-x
        X.append([x,l,r])
    D = [I()for _ in range(Q)]
    seg_min = SegmentTree(Q,inf,lambda a,b:min(a,b))
    for x,l,r in X:
        L = bisect.bisect_left(D,l)
        R = bisect.bisect_left(D,r)
        seg_min.update(L,R,x)
    ans = []
    for i in range(Q):
        cur = seg_min.query(i)
        if cur==inf:
            ans.append(-1)
        else:
            ans.append(cur)
    for v in ans:
        print(v)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examF()

"""

"""

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.buffer.readline

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

for i in range(N):
    s, t, x = map(int, input().split())
    E.append((0, t - x, x, i))
    E.append((1, s - x, x, i))

D = [int(input()) for _ in range(Q)]

E.sort(key=lambda a: a[1], reverse=True)

ans = []
que = [(10**18, -1)]
V = set()
for d in D:
    while E and E[-1][1] <= d:
        f, _, x, i = E.pop()
        if f == 0:
            V.add(i)
        else:
            heappush(que, (x, i))
    while que[0][1] in V:
        heappop(que)
    ans.append(que[0][0])

ans = [a if a < 10**18 else -1 for a in ans]
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

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

ans = [-1] * Q
skip = [-1] * Q

for S, T, X in STX:
    # [S - X, T - X)
    left = bisect_left(D, S - X)
    right = bisect_right(D, T - X - 1)

    while left < right:
        if skip[left] < 0:
            skip[left] = right
            ans[left] = X
            left += 1
        else:
            left = skip[left]

print(*ans, sep="\n")

Submission status: Accepted

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

n, q = map(int, input().split())
STX = [list(map(int, input().split())) for _ in range(n)]
D = list(map(int, read().split()))
E = []
for s, t, x in STX:
  E.append((s-x, x, 1))
  E.append((t-x, x, 0))
E.sort(reverse=True)
que = []
stop = set()
que.append(10**10)
stop.add(10**10)
for d in D:
  while E and E[-1][0] <= d:
    temp, x, f = E.pop()
    if f:
      heapq.heappush(que, x)
      stop.add(x)
    else:
      stop.remove(x)
  while que[0] not in stop:
    heapq.heappop(que)
  if que[0] == 10**10:
    print(-1)
  else:
    print(que[0])

Submission status: Accepted

Solution code:
def main():    
    import bisect
    import sys
    input = sys.stdin.readline
    n,q = map(int,input().split())
    l = [list(map(int,input().split())) for i in range(n)]
    l = sorted(l,key = lambda x: x[2])
    d = [int(input()) for i in range(q)]

    ans = [-1]*q
    skip = [-1]*q
    for s,t,x in l:
        le = bisect.bisect_left(d,s-x)
        ri = bisect.bisect_left(d,t-x)
        while le < ri:
            if skip[le] == -1:
                ans[le] = x
                skip[le] = ri
                le += 1
            else:
                le = skip[le]

    for i in ans:
        print(i)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Solution code:

from heapq import *
def main():
    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])

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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=[]
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(readline()),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: Accepted

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 = []
for s, t, x in STX:
    EVENT.append((s-x, 1, x))
    EVENT.append((t-x, 0, x))

for i in range(Q):
    d = int(readline())
    EVENT.append((d, 2, i))

ans = [-1] * Q

EVENT.sort()


STOP = set()
h = []
for t, op, x in EVENT:
    if op == 2 and STOP:
        while h and h[0] not in STOP:
            heappop(h)
        ans[x] = h[0]
    elif op == 1:
        STOP.add(x)
        heappush(h, x)
    elif op == 0:
        STOP.remove(x)

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

Submission status: Accepted

Solution code:
def main():
    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)

main()

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

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

nxt = [-1] * q
ans = [-1] * q

for s, t, x in stx:
    l = bisect_left(d, s - x)
    r = bisect_left(d, t - x)

    while l < r:
        if nxt[l] == -1:
            ans[l] = x
            nxt[l] = r
            l += 1
        else:
            l = nxt[l]

print(*ans, sep="\n")

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,Q = LI()
    q = LIR(n)
    q.sort(key = lambda x:x[2])
    d = IR(Q)
    ans = [-1]*(Q+1)
    f = [0]*Q
    for s,t,x in q:
        l = bisect.bisect_left(d,s-x)
        r = bisect.bisect_left(d,t-x)
        while l < r:
            while ans[l] != -1:
                l = f[l]
            if r <= l:
                break
            ans[l] = x
            f[l] = r
            l += 1
    for i in ans[:-1]:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

for i in range(Q):
    d = int(input())
    EVENT.append((d, 2, i))

ans = [-1] * Q

EVENT.sort()


STOP = set()
h = []
for t, op, x in EVENT:
    if op == 2 and STOP:
        while h and h[0] not in STOP:
            heappop(h)
        ans[x] = h[0]
    elif op == 1:
        STOP.add(x)
        heappush(h, x)
    elif op == 0:
        STOP.remove(x)

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

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
from heapq import heapify, heappush, heappop

read = sys.stdin.read

N, Q, *STXD = map(int, read().split())
STX = STXD[:3 * N]
queue = []

for i, (S, T, X) in enumerate(zip(*[iter(STX)] * 3), 1):
    queue.append((S - X - 0.5, X, i))
    queue.append((T - X - 0.5, -X, i))

for D in STXD[3 * N:]:
    queue.append((D, 0, 0))

queue.sort(key=itemgetter(0), reverse=True)
heap = []
heapify(heap)
stop, construction = -1, 0
not_available = set()
while queue:
    _, x, n = queue.pop()
    if x == 0:
        print(stop)
    elif x < 0:
        not_available.add(n)
        if n == construction:
            while heap:
                stop, construction = heappop(heap)
                if construction not in not_available:
                    break
            else:
                stop, construction = -1, 0
    else:
        if stop != -1:
            if stop <= x:
                heappush(heap, (x, n))
            else:
                heappush(heap, (stop, construction))
                stop, construction = x, n
        else:
            stop, construction = x, n

Submission status: Accepted

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

N, Q = (int(i) for i in input().split())
L = [0] * 2 * N
for i in range(N):
    S, T, X = (int(i) for i in input().split())
    L[2 * i] = (S-X, X, 1)
    L[2 * i + 1] = (T-X, X, 0)

L.sort(reverse=True)

Xs = set([])
XH = []
heapq.heapify(XH)
for i in range(Q):
    D = int(input())
    ans = 0
    while True:
        if L:
            t, X, f = L.pop()
            if t <= D:
                if f == 1:
                    Xs.add(X)
                    heapq.heappush(XH, X)
                else:
                    Xs.remove(X)
            else:
                L.append((t, X, f))
                break
        else:
            break
    if Xs:
        while XH[0] not in Xs:
            X = heapq.heappop(XH)
        print(XH[0])
    else:
        print("-1")

Submission status: Accepted

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

import heapq
N, Q = (int(i) for i in input().split())
L = [0] * (2 * N + Q)
for i in range(N):
    S, T, X = (int(i) for i in input().split())
    L[2 * i] = (S-X, 1, X)
    L[2 * i + 1] = (T-X, -1, X)
for i in range(Q):
    D = int(input())
    L[2 * N + i] = (D, 2, 0)
L.sort()

Xs = set([])
XH = []
heapq.heapify(XH)
for t, f, X in L:
    if f == 1:
        Xs.add(X)
        heapq.heappush(XH, X)
    elif  f == -1:
        Xs.remove(X)
    else:
        if Xs:
            while XH[0] not in Xs:
                X = heapq.heappop(XH)
            print(XH[0])
        else:
            print("-1")

Submission status: Accepted

Solution code:
class SegmentTreeDual():
    def __init__(self,arr,op=lambda x,y:y if y != -1 else x,ie=-1):
        self.h = (len(arr)-1).bit_length()
        self.n = 2**self.h
        self.ie = ie
        self.op = op
        self.val = [ie for _ in range(self.n)]
        self.laz = [ie for _ in range(2*self.n)]
        for i in range(len(arr)):
            self.val[i] = arr[i]

    def propagate(self,k):
        if self.laz[k] == self.ie: return
        if self.n <= k:
            self.val[k-self.n] = self.op(self.val[k-self.n],self.laz[k])
            self.laz[k] = self.ie
        else:
            self.laz[2*k] = self.op(self.laz[2*k],self.laz[k])
            self.laz[2*k+1] = self.op(self.laz[2*k+1],self.laz[k])
            self.laz[k] = self.ie

    def update(self,left,right,x):
        left += self.n
        right += self.n
        #可換なら不要?
        for i in range(self.h)[::-1]:
            self.propagate(left>>i)
            self.propagate(right>>i)
        #
        while right-left>0:
            if right & 1:
                right -= 1
                self.laz[right] = self.op(self.laz[right],x)
            if left & 1:
                self.laz[left] = self.op(self.laz[left],x)
                left += 1
            left >>= 1
            right >>= 1
    def get(self,index):
        res = self.val[index]
        index += self.n
        while index>0:
            res = self.op(res,self.laz[index])
            index //= 2
        return res


from bisect import bisect_left,bisect_right
import sys
input = sys.stdin.readline
INF = 10**18

N,Q = map(int,input().split())
P = [-INF,INF]
R = []

for i in range(N):
    s,t,x = map(int,input().split())
    R.append((s-x,t-x,x))
    P.append(s-x)
    P.append(t-x)
D = []
for i in range(Q):
    d = int(input())
    D.append(d)
    P.append(d)

R = sorted(R,key=lambda x:x[2],reverse=True)
P = sorted(set(P))
S = dict()
for i in range(len(P)):
    S[P[i]] = i

st = SegmentTreeDual(
                    arr = [-1 for _ in range(len(P))],
                    op = lambda x,y:y if y != -1 else x,
                    ie = -1
                    )
for i in range(N):
    st.update(S[R[i][0]],S[R[i][1]],R[i][2])

ans = []

for i in range(Q):
    ans.append(st.get(S[D[i]]))

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