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:
# Solution using a lazy segment tree

from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


class SegmentTree:  # 0-indexed
    def __init__(self, array, operation=min, identity=10**30):
        self.identity = identity
        self.n = len(array)
        self.N = 1 << (self.n - 1).bit_length()
        self.tree = [self.identity] * 2 * self.N
        self.lazy = [None] * 2 * self.N
        self.opr = operation
        for i in range(self.n):
            self.tree[i+self.N-1] = array[i]
        for i in range(self.N-2, -1, -1):
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])

    def values(self):
        for i in range(self.n-1):
            self.query(i, i+1)
        return self.tree[self.N-1:self.n+self.N-1]

    def getindex(self, l, r):
        l = (l + self.N)
        r = (r + self.N)
        lm = l // (l & -l) >> 1
        rm = r // (r & -r) >> 1
        while r-l > 0:
            if r <= rm:
                yield r
            if l <= lm:
                yield l
            l = l >> 1
            r = r >> 1
        while l:
            yield l
            l = l >> 1

    def propagates(self, *indices):
        for i in reversed(indices):
            i -= 1
            v = self.lazy[i]
            if v is None:
                continue
            self.lazy[2*i+1] = self.tree[2*i+1] = v >> 1
            self.lazy[2*i+2] = self.tree[2*i+2] = v >> 1
            self.lazy[i] = None

    def update(self, p, q, x):
        if p == q:
            return None
        indices = tuple(self.getindex(p, q))
        self.propagates(*indices)
        p += self.N-1
        q += self.N-2
        while q-p > 0:
            if p % 2 == 0:
                self.lazy[p] = self.tree[p] = x
            if q % 2 == 1:
                self.lazy[q] = self.tree[q] = x
            p = p//2
            q = q//2 - 1
            x <<= 1
        if p == q:
            self.lazy[p] = self.tree[p] = x
        for i in indices:
            i -= 1
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])

    def query(self, p, q):  # [p,q)
        if q <= p:
            print("Oops!  That was no valid number.  Try again...")
            exit()
        self.propagates(*self.getindex(p, q))
        p += self.N-1
        q += self.N-2
        res = self.identity
        while q-p > 0:
            if p % 2 == 0:
                res = self.opr(res, self.tree[p])
            if q % 2 == 1:
                res = self.opr(res, self.tree[q])
            p = p//2
            q = q//2 - 1
        if p == q:
            res = self.opr(res, self.tree[p])
        return res


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

Works = []
for _ in range(n):
    s, t, x = map(int, input().split())
    Works.append((s, t, x))
Works = sorted(Works, key=lambda w: -w[2])

People = []
for _ in range(q):
    People.append(int(input()))

ST = SegmentTree([-1]*q)

for s, t, x in Works:
    left = bisect_left(People, s-x)
    right = bisect_left(People, t-x)
    ST.update(left, right, x)

for x in ST.values():
    print(x)

Submission status: Accepted

Solution code:
# Solution using a lazy segment tree

from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


class SegmentTree:  # 0-indexed
    def __init__(self, array, operation=min, identity=10**30):
        self.identity = identity
        self.n = len(array)
        self.N = 1 << (self.n - 1).bit_length()
        self.tree = [self.identity] * 2 * self.N
        self.lazy = [None] * 2 * self.N
        self.opr = operation
        for i in range(self.n):
            self.tree[i+self.N-1] = array[i]
        for i in range(self.N-2, -1, -1):
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])

    def values(self):
        return self.tree[self.N-1:self.n+self.N-1]

    def getindex(self, l, r):
        l = (l + self.N)
        r = (r + self.N)
        lm = l // (l & -l) >> 1
        rm = r // (r & -r) >> 1
        while r-l > 0:
            if r <= rm:
                yield r
            if l <= lm:
                yield l
            l = l >> 1
            r = r >> 1
        while l:
            yield l
            l = l >> 1

    def propagates(self, *indices):
        for i in reversed(indices):
            i -= 1
            v = self.lazy[i]
            if v is None:
                continue
            self.lazy[2*i+1] = self.tree[2*i+1] = v >> 1
            self.lazy[2*i+2] = self.tree[2*i+2] = v >> 1
            self.lazy[i] = None

    def update(self, p, q, x):
        if p == q:
            return None
        indices = tuple(self.getindex(p, q))
        self.propagates(*indices)
        p += self.N-1
        q += self.N-2
        while q-p > 0:
            if p % 2 == 0:
                self.lazy[p] = self.tree[p] = x
            if q % 2 == 1:
                self.lazy[q] = self.tree[q] = x
            p = p//2
            q = q//2 - 1
            x <<= 1
        if p == q:
            self.lazy[p] = self.tree[p] = x
        for i in indices:
            i -= 1
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])

    def query(self, p, q):  # [p,q)
        if q <= p:
            print("Oops!  That was no valid number.  Try again...")
            exit()
        self.propagates(*self.getindex(p, q))
        p += self.N-1
        q += self.N-2
        res = self.identity
        while q-p > 0:
            if p % 2 == 0:
                res = self.opr(res, self.tree[p])
            if q % 2 == 1:
                res = self.opr(res, self.tree[q])
            p = p//2
            q = q//2 - 1
        if p == q:
            res = self.opr(res, self.tree[p])
        return res


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

Works = []
for _ in range(n):
    s, t, x = map(int, input().split())
    Works.append((s, t, x))
Works = sorted(Works, key=lambda w: -w[2])

People = []
for _ in range(q):
    People.append(int(input()))

ST = SegmentTree([-1]*q)

for s, t, x in Works:
    left = bisect_left(People, s-x)
    right = bisect_left(People, t-x)
    ST.update(left, right, x)

for i in range(q):
    print(ST.query(i, i+1))

Submission status: Accepted

Solution code:
import heapq
class HeapDict:
    def __init__(self):
        self.h = []
        self.d = {}

    def insert(self,x):
        if x not in self.d or self.d[x] == 0:
            heapq.heappush(self.h, x)
        self.d.setdefault(x,0)
        self.d[x] += 1


    def erase(self,x):
        if x not in self.d or self.d[x] == 0:
            return
        else:
            self.d[x] -= 1

        while self.h:
            if self.d[self.h[0]] == 0:
                heapq.heappop(self.h)
            else:
                break


    def get_min(self):
        if not self.h:
            return None
        else:
            return self.h[0]


    def pop(self):
        poped_val = self.h[0]
        self.erase(poped_val)
        return poped_val


    def exist(self, x):
        return (x in self.d and self.d[x] > 0)


    def show_h(self):
        elems = [v for v in self.h if self.d[v] > 0]
        print(elems)


    def show_d(self):
        print(self.d)



# def main():
n,q = map(int, input().split())
eventl = []

for _ in range(n):
    s,t,x = map(int, input().split())
    eventl.append((s-x, 'a-stop', x)) 
    eventl.append((t-x, 'b-start', x))

for i in range(q):
    d = int(input())
    eventl.append((d,'c-go', i))

eventl.sort()

ans = [0]*q
hd = HeapDict()
for e in eventl:
    if e[1] == 'a-stop':
        hd.insert(e[2])
    elif e[1] == 'b-start':
        hd.erase(e[2])
    else:
        min_x = hd.get_min()
        if min_x is not None:
            ans[e[2]] = min_x
        else:
            ans[e[2]] = -1

for a in ans:
    print(a)


# if __name__ == "__main__":
#     main()

Submission status: Accepted

Solution code:
import heapq, sys
input = sys.stdin.readline
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 _ in range(q):
    d = int(input())
    event.append((d, 2, 0))

event.sort(key=lambda x: (x[0], x[1]))
now = []
memo = set()

tmp = 0

for i, (t, flg, x) in enumerate(event):
    if flg == -1:
        memo.remove(x)
    elif flg == 1:
        heapq.heappush(now, x)
        memo.add(x)
    else:
        while len(now) > 0 and now[0] not in memo:
            heapq.heappop(now)
        if len(now) > 0:
            print(now[0])
        else:
            print(-1)

Submission status: Accepted

Solution code:
from bisect import*
b=bisect_left
n,q,*t=map(int,open(0).read().split())
p=t[-q:]
*a,=o=[-1]*q
for x,t,s in sorted(zip(*[iter(t[~q::-1])]*3)):
 l,r=b(p,s-x),b(p,t-x)
 while l<r:
  if~o[l]:l=o[l]
  else:a[l],o[l]=x,r;l+=1
print(*a)

Submission status: Accepted

Solution code:
import bisect
 
 
class SegTree:
 
    def __init__(self, n):
        # supposed that n = 2**m
        self.n = n
        self.val = [-1] * (2 * n - 1)
 
    def _update(self, a, b, v, k, l, r):
        # 区間[a, b)上の値をvに更新
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            self.val[k] = v
        else:
            self._update(a, b, v, 2 * k + 1, l, (l + r) // 2)
            self._update(a, b, v, 2 * k + 2, (l + r) // 2, r)
 
    def query(self, x):
        # ノードxの値を返す
        k = self.n + x - 1
        ret = self.val[k]
        while k > 0:
            k = (k - 1) // 2
            ret = max(ret, self.val[k])
        return ret
 
 
def main():
    N, Q = list(map(int, input().split(' ')))
    work_list = [list(map(int, input().split(' '))) for n in range(N)] 
    # 工事は出発地から遠い順に並べておく
    work_list.sort(key=lambda work: work[2], reverse=True)
    D = [int(input()) for q in range(Q)]
    # 一番最初に引っかかる工事のインデックスを求める
    QQ = 1
    while QQ < Q:
        QQ <<= 1
    tree = SegTree(QQ)
    for w, work in enumerate(work_list):
        s, t, x = work
        # s - x <= d < t - x だと工事に引っかかる
        left = bisect.bisect_left(D, s - x)
        right = bisect.bisect_left(D, t - x)
        tree._update(left, right, w, 0, 0, QQ)
    for q in range(Q):
        w = tree.query(q)
        if w == -1:
            print(-1)
        else:
            print(work_list[w][2])
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N, Q = map(int, input().split())
l, q = [], []
u = set()

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

for _, m, x in l:
    if m==0:
        u.remove(x)
    elif m==1:
        heappush(q, x)
        u.add(x)
    else:
        while q:
            if q[0] not in u:
                heappop(q)
            else:
                break
        print(q[0] if q else -1)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N, Q = map(int, input().split())
l, q = [], []
u = set()

for _ in range(N):
    S, T, X = map(int, input().split())
    l.append((S-X, 1, X))
    l.append((T-X, 0, X))

for i in range(Q):
    l.append((int(input()), 2, i))

l.sort()

for _, m, x in l:
    if m==0:
        u.remove(x)
    elif m==1:
        heappush(q, x)
        u.add(x)
    else:
        while q:
            if q[0] not in u:
                heappop(q)
            else:
                break
        print(q[0] if q else -1)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N, Q = map(int, input().split())
l = []
used = set()
q = []

for i in range(N):
    S, T, X = map(int, input().split())
    l.append((S-X, 1, X))
    l.append((T-X, 0, X))

for i in range(Q):
    l.append((int(input()), 2, i))

l.sort()

for pos, m, x in l:
    if m==0:
        used.remove(x)
    elif m==1:
        heappush(q, x)
        used.add(x)
    else:
        while q:
            if q[0] not in used:
                heappop(q)
            else:
                break
        print(q[0] if q else -1)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N, Q = map(int, input().split())
l = []
ans = [0]*Q
used = set()
q = []

for i in range(N):
    S, T, X = map(int, input().split())
    l.append((S-X, 1, X))
    l.append((T-X, 0, X))

for i in range(Q):
    v = int(input())
    l.append((v, 2, i))

l.sort()

for pos, m, x in l:
    if m==0:
        used.remove(x)
    elif m==1:
        heappush(q, x)
        used.add(x)
    else:
        while q:
            if q[0] not in used:
                heappop(q)
            else:
                break
        ans[x] = q[0] if q else -1

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from bisect import bisect_left, bisect_right
import heapq

INF = float("inf")


class ErasableHeap(object):
    # https://qiita.com/Salmonize/items/638da118cd621d2628d1
    def __init__(self):
        self.data = []
        self.event = []

    def push(self, x):
        return heapq.heappush(self.data, x)

    def erase(self, x):
        return heapq.heappush(self.event, x)

    def _check(self):
        while self.event and\
                self.data[0] == self.event[0]:
            heapq.heappop(self.data)
            heapq.heappop(self.event)

    def front(self):
        self._check()
        return self.data[0]

    def pop(self):
        self.check()
        return heapq.heappop(self.data)

    def __len__(self):
        self._check()
        return len(self.data)


def main():

    N, Q = map(int, input().split())
    event = []
    for i in range(N):
        s, t, x = map(int, input().split())
        event.append((s-x, 1, x))
        event.append((t-x, -1, x))
    # 番兵用のeventを追加しておく
    event.append((INF, +1, INF))
    event.sort()

    D = [0]*Q
    for i in range(Q):
        D[i] = int(input())

    head = 0
    stack = ErasableHeap()
    for t, p, x in event:
        while head < Q and D[head] < t:
            if len(stack) == 0:
                print(-1)
            else:
                print(stack.front())
            head += 1
        if p == 1:
            stack.push(x)
        else:
            stack.erase(x)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from bisect import bisect_left, bisect_right
import heapq

INF = float("inf")


class ErasableHeap(object):
    # https://qiita.com/Salmonize/items/638da118cd621d2628d1
    def __init__(self):
        self.data = []
        self.event = []

    def push(self, x):
        return heapq.heappush(self.data, x)

    def erase(self, x):
        return heapq.heappush(self.event, x)

    def _check(self):
        while self.event and\
                self.data[0] == self.event[0]:
            heapq.heappop(self.data)
            heapq.heappop(self.event)

    def front(self):
        self._check()
        return self.data[0]

    def pop(self):
        self.check()
        return heapq.heappop(self.data)

    def __len__(self):
        self._check()
        return len(self.data)


def main():
    N, Q = map(int, input().split())
    XST = [0]*N
    for i in range(N):
        s, t, x = map(int, input().split())
        XST[i] = (x, s-x, t-x)
    D = [0]*Q
    for i in range(Q):
        D[i] = int(input())
    event = []
    for x, s, t in XST:
        event.append((s, 1, x))
        event.append((t, -1, x))

    event.sort()

    head = 0
    stack = ErasableHeap()
    for t, p, x in event:
        while D[head] < t:
            if len(stack) == 0:
                print(-1)
            else:
                print(stack.front())
            head += 1
            if head >= Q:
                return
        if p == 1:
            stack.push(x)
        else:
            stack.erase(x)

    while head < len(D):
        if len(stack) == 0:
            print(-1)
        else:
            print(stack.front())
        head += 1
        if head >= Q:
            return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    def update(self, k: int, x):
        k += self.N0 - 1
        ################################################################
        self.data[k] = x
        ################################################################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ################################################################
        
        while L < R:
            if L & 1:
                res = self.segfunc(res, self.data[L - 1])
                L += 1
            if R & 1:
                R -= 1
                res = self.segfunc(res, self.data[R - 1])
            L >>= 1
            R >>= 1
        
        ################################################################
        return res


def solve():
    N, Q = map(int, rl().split())
    events = []
    xs = set()
    for _ in range(N):
        s, t, x = map(int, rl().split())
        events.append((t - x, 0, x))
        events.append((s - x, 1, x))
        xs.add(x)
    for _ in range(Q):
        d = int(rl())
        events.append((d, 2, -1))
    events.sort(key=itemgetter(0, 1))
    
    x_to_idx = {x: idx for idx, x in enumerate(sorted(xs))}
    M = len(xs)
    ide_ele = 10 ** 10
    seg_tree = SegmentTree([ide_ele] * M, min, ide_ele)
    
    ans = []
    for _, com, pos in events:
        if com == 0:
            seg_tree.update(x_to_idx[pos], ide_ele)
        elif com == 1:
            seg_tree.update(x_to_idx[pos], pos)
        else:
            tmp = seg_tree.data[0]
            ans.append(tmp if tmp != ide_ele else -1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

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

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

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

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

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

Submission status: Accepted

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

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



    import bisect

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

    for i in range(q):
        res = query(i)
        if res == 10**9 + 1:
            print(-1)
        else:
            print(res)

main()

Submission status: Accepted

Solution code:

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

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



import bisect

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

for i in range(q):
    res = query(i)
    if res == 10**9 + 1:
        print(-1)
    else:
        print(res)