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: Runtime Error

Solution code:
import sys


class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.lst = None
        self.rst = None
        self.bias = 0


class AVLTree:
    def __init__(self):
        self.root = None

    def rotate_left(self, v):
        u = v.rst
        v.rst = u.lst
        u.lst = v
        if u.bias == -1:
            u.bias = v.bias = 0
        else:
            u.bias = 1
            v.bias = -1
        return u

    def rotate_right(self, v):
        u = v.lst
        v.lst = u.rst
        u.rst = v
        if u.bias == 1:
            u.bias = v.bias = 0
        else:
            u.bias = -1
            v.bias = 1
        return u

    def rotateLR(self, v):
        u = v.lst
        t = u.rst
        u.rst = t.lst
        t.lst = u
        v.lst = t.rst
        t.rst = v
        self.update_bias_double(t)
        return t

    def rotateRL(self, v):
        u = v.rst
        t = u.lst
        u.lst = t.rst
        t.rst = u
        v.rst = t.lst
        t.lst = v
        self.update_bias_double(t)
        return t

    def update_bias_double(self, v):
        if v.bias == 1:
            v.rst.bias = -1
            v.lst.bias = 0
        elif v.bias == -1:
            v.rst.bias = 0
            v.lst.bias = 1
        else:
            v.rst.bias = 0
            v.lst.bias = 0
        v.bias = 0

    def insert(self, key, val):
        if self.root is None:
            self.root = Node(key, val)
            return

        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lst
            elif v.key < key:
                history.append((v, -1))
                v = v.rst
            elif v.key == key:
                v.val = val
                return

        p, pdir = history[-1]
        if pdir == 1:
            p.lst = Node(key, val)
        else:
            p.rst = Node(key, val)

        while history:
            v, direction = history.pop()
            v.bias += direction

            print(v, history)
            print(avl)
            print('#############')
            new_v = None
            b = v.bias
            if b == 0:
                break

            if b == 2:
                u = v.lst
                if u.bias == -1:
                    new_v = self.rotateLR(v)
                else:
                    new_v = self.rotate_right(v)
                break
            if b == -2:
                u = v.rst
                if u.bias == 1:
                    new_v = self.rotateRL(v)
                else:
                    new_v = self.rotate_left(v)
                break

        if new_v is not None:
            if len(history) == 0:
                self.root = new_v
                return
            p, pdir = history.pop()
            if pdir == 1:
                p.lst = new_v
            else:
                p.rst = new_v

    def delete(self, key):
        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lst
            elif v.key < key:
                history.append((v, -1))
                v = v.rst
            else:
                break
        else:
            return False

        if v.lst is not None:
            history.append((v, 1))
            lmax = v.lst
            while lmax.rst is not None:
                history.append((lmax, -1))
                lmax = lmax.rst

            v.key = lmax.key
            v.val = lmax.val

            v = lmax

        c = v.rst if v.lst is None else v.lst

        if history:
            p, pdir = history[-1]
            if pdir == 1:
                p.lst = c
            else:
                p.rst = c

        else:
            self.root = c
            return True

        while history:
            new_p = None

            p, pdir = history.pop()
            p.bias -= pdir

            b = p.bias
            if b == 2:
                if p.lst.bias == -1:
                    new_p = self.rotateLR(p)
                else:
                    new_p = self.rotate_right(p)

            elif b == -2:
                if p.rst.bias == 1:
                    new_p = self.rotateRL(p)
                else:
                    new_p = self.rotate_left(p)

            elif b != 0:
                break

            if new_p is not None:
                if len(history) == 0:
                    self.root = new_p
                    return True
                gp, gpdir = history[-1]
                if gpdir == 1:
                    gp.lst = new_p
                else:
                    gp.rst = new_p
                if new_p.bias != 0:
                    break
        return True

    def member(self, key):
        v = self.root
        while v is not None:
            if key < v.key:
                v = v.lst
            elif v.key < key:
                v = v.rst
            else:
                return True
        return False

    def get(self, key):
        v = self.root
        while v is not None:
            if key < v.key:
                v = v.lst
            elif v.key < key:
                v = v.rst
            else:
                return v.val
        return None

    def lower_bound(self, key):
        ret = (float('inf'), 0)
        v = self.root
        while v is not None:
            if v.key >= key:
                if ret > v.key:
                    ret = v.key
                v = v.lst
            else:
                v = v.rst
        return ret

    def upper_bound(self, key):
        ret = -float('inf')
        v = self.root
        while v is not None:
            if v.key <= key:
                if ret < v.key:
                    ret = v.key
                v = v.rst
            else:
                v = v.lst
        return ret

    def __contains__(self, key): return self.member(key)
    def __getitem__(self, key): return self.get(key)
    def __setitem__(self, key, val): return self.insert(key, val)
    def __delitem__(self, key): return self.delete(key)
    def __bool__(self): return self.root is not None

    def __str__(self):
        return self.tostr_rec("", "", self.root)

    def tostr_rec(self, head, bar, t):
        graph = ""

        if t != None:
            graph += self.tostr_rec(head + "    ", "／", t.rst)
            node = str(t.key) + ":" + str(t.bias)
            graph += head + bar + node + "\n"
            graph += self.tostr_rec(head + "    ", "＼", t.lst)

        return graph


read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline
N, Q = map(int, input().split())
S = []
T = []
for i in range(N):
    s, t, x = map(int, input().split())
    S.append((s-x, s, x))
    T.append((t-x, s, x))

S.sort(reverse=True)
T.sort(reverse=True)

INF = 10**10
avl = AVLTree()
ans = []
for d in map(int, read().split()):
    while S and S[-1][0] <= d:
        sx, s, x = S.pop()
        avl[(x, sx+x)] = x
        print(avl)
    while T and T[-1][0] <= d:
        tx, s, x = T.pop()
        print(avl)
        del avl[(x, s)]
    x, s = avl.lower_bound((-INF, 0))
    ans.append(x if x < INF else -1)

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

Submission status: Runtime Error

Solution code:
import sys


class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.lst = None
        self.rst = None
        self.bias = 0


class AVLTree:
    def __init__(self):
        self.root = None

    def rotate_left(self, v):
        u = v.rst
        v.rst = u.lst
        u.lst = v
        if u.bias == -1:
            u.bias = v.bias = 0
        else:
            u.bias = 1
            v.bias = -1
        return u

    def rotate_right(self, v):
        u = v.lst
        v.lst = u.rst
        u.rst = v
        if u.bias == 1:
            u.bias = v.bias = 0
        else:
            u.bias = -1
            v.bias = 1
        return u

    def rotateLR(self, v):
        u = v.lst
        t = u.rst
        u.rst = t.lst
        t.lst = u
        v.lst = t.rst
        t.rst = v
        self.update_bias_double(t)
        return t

    def rotateRL(self, v):
        u = v.rst
        t = u.lst
        u.lst = t.rst
        t.rst = u
        v.rst = t.lst
        t.lst = v
        self.update_bias_double(t)
        return t

    def update_bias_double(self, v):
        if v.bias == 1:
            v.rst.bias = -1
            v.lst.bias = 0
        elif v.bias == -1:
            v.rst.bias = 0
            v.lst.bias = 1
        else:
            v.rst.bias = 0
            v.lst.bias = 0
        v.bias = 0

    def insert(self, key, val):
        if self.root is None:
            self.root = Node(key, val)
            return

        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lst
            elif v.key < key:
                history.append((v, -1))
                v = v.rst
            elif v.key == key:
                v.val = val
                return

        p, pdir = history[-1]
        if pdir == 1:
            p.lst = Node(key, val)
        else:
            p.rst = Node(key, val)

        while history:
            v, direction = history.pop()
            v.bias += direction

            new_v = None
            b = v.bias
            if b == 0:
                break

            if b == 2:
                u = v.lst
                if u.bias == -1:
                    new_v = self.rotateLR(v)
                else:
                    new_v = self.rotate_right(v)

            if b == -2:
                u = v.rst
                if u.bias == 1:
                    new_v = self.rotateRL(v)
                else:
                    new_v = self.rotate_left(v)

            if new_v is not None:
                if len(history) == 0:
                    self.root = new_v
                    return
                p, pdir = history.pop()
                if pdir == 1:
                    p.lst = new_v
                else:
                    p.rst = new_v

    def delete(self, key):
        v = self.root
        history = []
        while v is not None:
            if key < v.key:
                history.append((v, 1))
                v = v.lst
            elif v.key < key:
                history.append((v, -1))
                v = v.rst
            else:
                break
        else:
            return False

        if v.lst is not None:
            history.append((v, 1))
            lmax = v.lst
            while lmax.rst is not None:
                history.append((lmax, -1))
                lmax = lmax.rst

            v.key = lmax.key
            v.val = lmax.val

            v = lmax

        c = v.rst if v.lst is None else v.lst

        if history:
            p, pdir = history[-1]
            if pdir == 1:
                p.lst = c
            else:
                p.rst = c

        else:
            self.root = c
            return True

        while history:
            new_p = None

            p, pdir = history.pop()
            p.bias -= pdir

            b = p.bias
            if b == 2:
                if p.lst.bias == -1:
                    new_p = self.rotateLR(p)
                else:
                    new_p = self.rotate_right(p)

            elif b == -2:
                if p.rst.bias == 1:
                    new_p = self.rotateRL(p)
                else:
                    new_p = self.rotate_left(p)

            elif b != 0:
                break

            if new_p is not None:
                if len(history) == 0:
                    self.root = new_p
                    return True
                gp, gpdir = history[-1]
                if gpdir == 1:
                    gp.lst = new_p
                else:
                    gp.rst = new_p
                if new_p.bias != 0:
                    break
        return True

    def member(self, key):
        v = self.root
        while v is not None:
            if key < v.key:
                v = v.lst
            elif v.key < key:
                v = v.rst
            else:
                return True
        return False

    def get(self, key):
        v = self.root
        while v is not None:
            if key < v.key:
                v = v.lst
            elif v.key < key:
                v = v.rst
            else:
                return v.val
        return None

    def lower_bound(self, key):
        ret = (float('inf'), 0)
        v = self.root
        while v is not None:
            if v.key >= key:
                if ret > v.key:
                    ret = v.key
                v = v.lst
            else:
                v = v.rst
        return ret

    def upper_bound(self, key):
        ret = -float('inf')
        v = self.root
        while v is not None:
            if v.key <= key:
                if ret < v.key:
                    ret = v.key
                v = v.rst
            else:
                v = v.lst
        return ret

    def __contains__(self, key): return self.member(key)
    def __getitem__(self, key): return self.get(key)
    def __setitem__(self, key, val): return self.insert(key, val)
    def __delitem__(self, key): return self.delete(key)
    def __bool__(self): return self.root is not None

    def __str__(self):
        return self.tostr_rec("", "", self.root)

    def tostr_rec(self, head, bar, t):
        graph = ""

        if t != None:
            graph += self.tostr_rec(head + "    ", "／", t.rst)
            node = str(t.key) + ":" + str(t.val)
            graph += head + bar + node + "\n"
            graph += self.tostr_rec(head + "    ", "＼", t.lst)

        return graph


read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline
N, Q = map(int, input().split())
S = []
T = []
for i in range(N):
    s, t, x = map(int, input().split())
    S.append((s-x, s, x))
    T.append((t-x, s, x))

S.sort(reverse=True)
T.sort(reverse=True)

INF = 10**10
avl = AVLTree()
ans = []
for d in map(int, read().split()):
    while S and S[-1][0] <= d:
        sx, s, x = S.pop()
        avl[(x, sx+x)] = x
    while T and T[-1][0] <= d:
        tx, s, x = T.pop()
        del avl[(x, s)]
    x, s = avl.lower_bound((-INF, 0))
    ans.append(x if x < INF else -1)

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

Submission status: Runtime Error

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

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

class segtree:
    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2**(len(nb)-1)
        else:
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity
        self.operator =operator

    def update(self,x,val):
        actual_x = x+self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        width_of_floor = self.num_end_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]


        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)

INF=10**10
          
s_tree = segtree(10**6,min,INF)

for i in range(N):
  s,t,q = map(int,input().split())
  
  i1,i2=max(s-q,0),max(t-q,0)
  for j in range(i1,i2):
    s_tree.update(j,q)
    
for i in range(Q):
  d = int(input())
  ans = s_tree.get(d,d+1)
  if ans == INF:print(-1)
  else:print(ans)

Submission status: Runtime Error

Solution code:
N,Q=map(int,input().split())

class segtree:
    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2**(len(nb)-1)
        else:
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity
        self.operator =operator

    def update(self,x,val):
        actual_x = x+self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        width_of_floor = self.num_end_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]


        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)

INF=10**10
          
s_tree = segtree(10**6,min,INF)

for i in range(N):
  s,t,q = map(int,input().split())
  
  i1,i2=max(s-q,0),max(t-q,0)
  for j in range(i1,i2):
    s_tree.update(j,q)
    
for i in range(Q):
  d = int(input())
  ans = s_tree.get(d,d+1)
  if ans == INF:print(-1)
  else:print(ans)

Submission status: Runtime Error

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):
        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: Runtime Error

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 _ in range(q):
    d = int(input())
    event.append((d, 2, 0))

event.sort()
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.put(x)

    else:
        while now[0] in memo:
            heapq.heappop(now)
        if len(now) > 0:
            print(now[0])
        else:
            print(-1)

Submission status: Runtime Error

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


def main():
    N, Q = map(int, input().split())
    XST = []
    for i in range(N):
        s, t, x = map(int, input().split())
        XST.append((x, s-x, t-x))
    XST.sort(reverse=True)
    D = [0]*Q
    for i in range(Q):
        D[i] = int(input())
    start = [set() for _ in range(Q)]
    end = [set() for _ in range(Q)]
    # Dはソートされている。
    for x, s, t in XST:
        # こっから！
        frm = bisect_left(D, s)
        to = bisect_left(D, t, lo=frm)
        # 数列の範囲を代入で更新して、値を取得する
        start[frm].add(x)
        end[to].add(x)
        # print(*stop, sep="\n")
        # for j in range(frm, to):
        #     stop[j] = x
    curr = set()
    for i in range(Q):
        curr |= start[i] - (start[i] & end[i])
        curr -= (end[i]-start[i])
        if len(curr) == 0:
            print(-1)
        else:
            print(min(curr))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
from heapq import heappush, heappop
from collections import defaultdict
 
n,q = map(int,readline().split())
data = list(map(int,read().split()))
A = data[:3*n]
D = data[3*n:]

E = []
F = {}
for i in range(n):
    s = A[i][0]
    t = A[i][1]
    x = A[i][2]
    F[x] = 0
    E.append((s-x, x, 1))
    E.append((t-x, x, -1))
E.append((10**10, 10**10, 1))

E.sort()

# print(E)

from heapq import heappush, heappop
Q = []

j = 0
for i in range(q):
    # print(F,j)
    while E[j][0] <= D[i]:
        if E[j][2] == 1:
            F[E[j][1]] += 1
            heappush(Q, E[j][1])
        else:
            F[E[j][1]] -= 1
        j += 1
    
    while len(Q) > 0 and F[Q[0]] == 0:
        _ = heappop(Q)
    if len(Q) == 0:
        print(-1)
    else:
        print(Q[0])

Submission status: Runtime Error

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

N, Q = MAP()

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

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

event.sort()
p = []
q = []
for t, c, x in event:
	if c == 0:
		heappush(p, x)
	elif c == 1:
		heappush(q, x)
	else:
        while q and p[0] == q[0]:
            heappop(p)
            heappop(q)
		print(-1 if not p else p[0])

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
import numpy as np

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

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

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

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

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter
import heapq

def main():
    N,Q = map(int,input().split())
    event = []
    
    for _ in range(N):
        s,t,x = map(int,input().split())
        event.append((s-x,0,x))
        event.append((t-x,1,x))
        
    for i in range(Q):
        a = int(input())
        event.append((a,2,i))
    
    event.sort(key=itemgetter(0))
    ans = [-1]*Q
    use = set()
    stop = []
    heapq.heapify(stop)
    
    for a,b,c in event:
        if b == 0:
            use.add(c)
            heapq.heappush(stop,c)
        elif b == 1:
            use.remove(c)
        else:
            while stop and stop[0] not in use:
                heapq.heappop(stop)
            ans[c] = -1 if len(stop) == 0 else stop[0]
    
    for num in ans:
        print(num)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline
from operator import itemgetter
import heapq

def main():
    N,Q = map(int,input().split())
    event = []
    
    for _ in range(N):
        s,t,x = map(int,input().split())
        event.append((s-x,0,x))
        event.append((t-x,1,x))
        
    for i in range(Q):
        a = int(input())
        event.append((a,2,-1))
    
    event.sort(key=itemgetter(0))
    
    use = set()
    stop = []
    heapq.heapify(stop)
    
    for a,b,c in event:
        if b == 0:
            use.add(c)
            heapq.heappush(stop,c)
        elif b == 1:
            use.remove(c)
        else:
            while stop and stop[0] not in use:
                heapq.heappop(stop)
            if stop == []:
                print(-1)
            else:
                print(stop[0])

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(300000)
from heapq import heappush, heappop
from collections import defaultdict

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, Q = MI()
events = list()
for _ in range(N):
    S, T, X = MI()
    # [S - X, T - X) に出発する人が影響を受ける
    events.append((S - X, 1, X))
    events.append((T - X, 2, X))
for i, d in enumerate([I() for _ in range(Q)]):
    events.append((d, 3, i))

ans = [0] * Q
events.sort()
blocks = defaultdict(int)
blockq = list()
for e1, type, e3 in events:
    if type == 1:
        X = e3
        blocks[X] += 1
        heappush(blockq, X)
    elif type == 2:
        X = e3
        if blocks[X] > 1:
            blocks[X] -= 1
        else:
            del blocks[X]
    else:
        i = e3
        if len(blocks) == 0:
            ans[i] = -1
        else:
            while True:
                block = heappop(blockq)
                if block in blocks:
                    break
            ans[i] = block

for a in ans:
    print(a)