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:
from collections import defaultdict
from heapq import heappush,heappop

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

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

events = sorted(events)
INF = 10**13
q = [INF]
cnt = defaultdict(int)
ans = [INF]*Q
for a,b,c in events:
    if b == 0:
        heappush(q,c)
        cnt[c] += 1
    elif b==1:
        cnt[c] -= 1
    else:
        while len(q) > 1 and cnt[q[0]] == 0:
            heappop(q)
        if q[0] == INF:
            ans[c] = -1
        else:
            ans[c] = q[0]
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

events = sorted(events)

q = [INF]
cnt = defaultdict(int)
cnt[INF] = 1
ans = [INF] * Q
for a, b, c in events:
    if b == 0:
        heapq.heappush(q, c)
        cnt[c] += 1
    if b == 1:
        cnt[c] -= 1
    if b == 2:
        while cnt[q[0]] == 0:
            heapq.heappop(q)
        if q[0] == INF:
            ans[c] = -1
        else:
            ans[c] = q[0]
for i in range(Q):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

events = sorted(events)

q = [INF]
cnt = defaultdict(int)
ans = [INF] * Q
for a, b, c in events:
    if b == 0:
        heapq.heappush(q, c)
        cnt[c] += 1
    if b == 1:
        cnt[c] -= 1
    if b == 2:
        while len(q) > 1 and cnt[q[0]] == 0:
            heapq.heappop(q)
        if q[0] == INF:
            ans[c] = -1
        else:
            ans[c] = q[0]
for i in range(Q):
    print(ans[i])

Submission status: Accepted

Solution code:
class DualSegmentTree():

    def __init__(self, n, op, e):
        """
        :param n: 配列の要素数
        :param op: 作用素（モノイド＝結合則＋単位元存在）
        :param e:  単位元
        """
        self.n = n
        self.op = op
        self.e = e
        self.depth = (self.n - 1).bit_length()
        self.size = 1 << self.depth
        self.lazy = [self.e] * ((self.size << 1) + 1)

    def built(self, array):
        """
        arrayを初期値とするセグメント木を構築
        """
        n, size, lazy = self.n, self.size, self.lazy
        for i in range(n):
            lazy[size + i] = array[i]

    def update(self, l, r, x):
        """
        半開区間 [l, r) の各々の要素 a に op(x, a)を作用させる （ 0-indexed ）　（ O(logN) ）
        """
        op, lazy = self.op, self.lazy
        l += self.size
        r += self.size
        self.propagate(l//(l&-l))
        self.propagate((r//(r&-r))-1)
        while l < r:
            if r&1:
                r -= 1              # 半開区間なので先に引いてる
                lazy[r] = op(x, lazy[r])
            if l&1:
                lazy[l] = op(x, lazy[l])
                l += 1
            l >>= 1
            r >>= 1

    def propagate(self, i):
        """
        根から葉に伝搬させる。可換モノイドの場合は更新時の伝搬をサボれる。　（ O(logN) ）
        """
        e, op, lazy = self.e, self.op, self.lazy
        for k in range(i.bit_length()-1, 0,-1):
            x = i>>k
            if lazy[x] == e:
                continue
            lazy[(x<<1)|1] = op(lazy[x], lazy[(x<<1)|1])
            lazy[x<<1] = op(lazy[x], lazy[x<<1])
            lazy[x] = e

    def get(self, i):
        """
        i 番目の値を取得（ 0-indexed ） ( O(logN) )
        """
        i += self.size
        self.propagate(i)
        return self.lazy[i]

    def __getitem__(self, i):
        return self.get(i)

    def __iter__(self):
        n, size, e, op, lazy = self.n, self.size, self.e, self.op, self.lazy
        for x in range(1, size):
            if lazy[x] == e:
                continue
            lazy[(x<<1)|1] = op(lazy[x], lazy[(x<<1)|1])
            lazy[x<<1] = op(lazy[x], lazy[x<<1])
            lazy[x] = e
        for a in lazy[size:size+n]:
            yield a

    def __str__(self):
        n, size, e, op, lazy = self.n, self.size, self.e, self.op, self.lazy
        for x in range(1, size):
            if lazy[x] == e:
                continue
            lazy[(x << 1) | 1] = op(lazy[x], lazy[(x << 1) | 1])
            lazy[x << 1] = op(lazy[x], lazy[x << 1])
            lazy[x] = e
        return str(lazy[size:size + n])

##################################################################################################################
import sys
from bisect import *
input = sys.stdin.readline

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

e = -1
op = lambda x, y: x if x != e else y
st = DualSegmentTree(Q, op, e)

Qu = [list(map(int, input().split())) for _ in range(N)]
Qu.sort(key=lambda x:x[2], reverse=True)

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

for q in Qu:
    S, T, X = q
    L = bisect_left(D,S-X)
    R = bisect_left(D,T-X)
    st.update(L, R, X)
print(*st, sep="\n")

Submission status: Accepted

Solution code:

class LazySegmentTree:
    """
    op: 区間取得クエリでreduceする際に使う演算子
    apply: 更新則の(n回)適用
    comp: 更新則の合成
    rep: f(x,m)+f(y,m) != f(x+y,m)となる場合に、m^nを高速に計算する用
    
    range_query: reduce(op, (apply(x,m) for x,m in zip(X,M)))
    
    満たすべき性質:
    
    集合X (要素)
    op[+]: X,X -> X
    (X, op)はモノイド
    
    集合M (更新則)
    comp[*]: M,M -> M
    (M, compose)はモノイド
    
    apply[f(x,m,n)]: X,M,Z+ -> X
    (Z+は区間長)
    
    f(x,e_M,n) = x
    f(x,m*n,p) = f(f(x,m,p),n,p)
    f(x,m,p)+f(y,m,q) = f(x+y,m,p+q)
    
    参考: https://algo-logic.info/segment-tree/#toc_id_3
    """
    @classmethod
    def all_identity(cls, op, op_e, comp, comp_e, apply, size):
        size = 1 << (size-1).bit_length()
        return cls(
            op,
            op_e,
            comp,
            comp_e,
            apply,
            [op_e]*(2*size),
            [comp_e]*size
        )

    @classmethod
    def from_initial_data(cls, op, op_e, comp, comp_e, apply, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [op_e]*(2*size)
        temp[size:size+len(data)] = data

        for i in reversed(range(size)):
            temp[i] = op(temp[2*i],temp[2*i+1])
        return cls(
            op,
            op_e,
            comp,
            comp_e,
            apply,
            temp,
            [comp_e]*size
        )

    # これ使わずファクトリーメソッド使いましょうね
    def __init__(self, op, op_e, comp, comp_e, apply, data, lazy):
        self.op = op
        self.op_e = op_e
        self.comp = comp
        self.comp_e = comp_e
        self.apply = apply
        self.data = data
        self.lazy = lazy
        self.size = len(self.data)//2
        self.depth = self.size.bit_length()-1
        self._l_indices = [0]*self.depth
        self._r_indices = [0]*self.depth
    
    def _update_indices(self, i, l):
        m = i//(i&-i)
        i >>= 1
        for k in range(self.depth):
            l[k] = i if i < m else 0
            i >>= 1
    
    
    def _propagate_top_down(self):
        data = self.data
        lazy = self.lazy
        apply = self.apply
        comp = self.comp
        comp_e = self.comp_e
        k = self.size >> 1
        
        for i,j in zip(reversed(self._l_indices), reversed(self._r_indices)):
            if i > 0:
                temp = self.lazy[i]
                if temp != comp_e:
                    lazy[i] = comp_e
                    a = i << 1
                    b = a | 1
                    data[a] = apply(data[a], temp, k)
                    data[b] = apply(data[b], temp, k)
                    if k > 1:
                        lazy[a] = comp(lazy[a], temp)
                        lazy[b] = comp(lazy[b], temp)
            if i < j:
                temp = self.lazy[j]
                if temp != comp_e:
                    lazy[j] = comp_e
                    a = j << 1
                    b = a | 1
                    data[a] = apply(data[a], temp, k)
                    data[b] = apply(data[b], temp, k)
                    if k > 1:
                        lazy[a] = comp(lazy[a], temp)
                        lazy[b] = comp(lazy[b], temp)
            k >>= 1
            
    def _propagate_bottom_up(self):
        data = self.data
        op = self.op
        for i,j in zip(self._l_indices, self._r_indices):
            if i < j:
                data[j] = op(data[j<<1],data[j<<1|1])
            if i > 0:
                data[i] = op(data[i<<1],data[i<<1|1])
    
    def update_interval(self, l, r, m):
        lazy = self.lazy
        data = self.data
        comp = self.comp
        apply = self.apply
        
        l += self.size
        r += self.size
        self._update_indices(l, self._l_indices)
        self._update_indices(r, self._r_indices)
        self._propagate_top_down()
        k = 1
        while l < r:
            if l & 1:
                data[l] = apply(data[l],m,k)
                if k > 1:
                    lazy[l] = comp(lazy[l],m)
                l += 1
            if r & 1:
                r -= 1
                data[r] = apply(data[r],m,k)
                if k > 1:
                    lazy[r] = comp(lazy[r],m)
            l >>= 1
            r >>= 1
            k <<= 1
        self._propagate_bottom_up()
    
    def get_interval(self, l, r):
        data = self.data
        op = self.op
        
        l += self.size
        r += self.size
        self._update_indices(l, self._l_indices)
        self._update_indices(r, self._r_indices)
        self._propagate_top_down()
        
        lx = self.op_e
        rx = self.op_e
        while l < r:
            if l & 1:
                lx = op(lx, data[l])
                l += 1
            if r & 1:
                r -= 1
                rx = op(data[r], rx)
            l >>= 1
            r >>= 1
        return op(lx,rx)



import sys
from bisect import *
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y
input = sys.stdin.readline

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

st = LazySegmentTree.all_identity(max2,-1, lambda x,m: x if m < 0 else m,-1,lambda x,m,l: x if m < 0 else m,Q)

Qu = [list(map(int, input().split())) for _ in range(N)]
Qu.sort(key=lambda x:x[2], reverse=True)

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

for q in Qu:
    S, T, X = q
    L = bisect_left(D,S-X)
    R = bisect_left(D,T-X)
    st.update_interval(L, R, X)
print(*(st.get_interval(i,i+1) for i in range(Q)), sep="\n")

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

N, Q = getNM()
sec = [getList() for i in range(N)]
section = []
for i in range(N):
    s, t, x = sec[i]
    section.append([s - x, t - x])
query = getArray(Q)

# 各queryがどのsectionの開区間[s, t)内にあるか
def event_sort(section, query):
    s_n = len(section)
    q_n = len(query)
    task = []
    for i in range(s_n):
        s, t = section[i]
        task.append((s, 0, i))
        task.append((t, 1, i))
    for i in range(q_n):
        task.append((query[i], 2, i))
    task.sort()

    se = set()
    
    ### この問題専用 ###
    res = [-1] * q_n # 答え
    ignore = [-1] * s_n # まだ区間が生きているか
    se_hp = [] # ignoreを元にまだ生きている区間の中でのxの最小値を求める
    heapq.heapify(se_hp)
    ##################

    for a, b, c in task:
        if b == 1:
            se.remove(c)
            ignore[c] = 1 # これは無視していい
        elif b == 0:
            se.add(c)
            heapq.heappush(se_hp, (sec[c][2], c)) # xの値をsecから引っ張る
        else:
            # 小さい順から抜け殻を捨てて回る
            while se_hp and ignore[se_hp[0][1]] == 1:
                heapq.heappop(se_hp)
            if se_hp:
                res[c] = se_hp[0][0]
            else:
                res[c] = -1
    return res

for i in event_sort(section, query):
    print(i)

"""
# 各queryがどのsectionの開区間[s, t)内にあるか
def event_sort(section, query):
    s = len(section)
    q = len(query)
    # イベント生成
    task = []
    for i in range(s):
        s, t = section[i]
        task.append((s, 0, i))
        task.append((t, 1, i))
    for i in range(q):
        task.append((query[i], 2, i))
    task.sort()

    # 引っかかってる場所の管理
    se = set()

    for a, b, c in task:
        # ゴールが来ると削除
        if b == 1:
            se.remove(c)
        # スタートが来ると追加
        elif b == 0:
            se.add(c)
        # queについてなら
        else:
            print(se)

section = [
[-3, 3],
[-1, 1],
[5, 7],
[1, 2],
]

query = [0, 1, 2, 3]
# [{0, 1}, {0, 3}, {0}, set()]
event_sort(section, query)
"""

Submission status: Accepted

Solution code:
import sys
INF = 1 << 30


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


read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
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.sort(reverse=True)

avl = AVLTree()
ans = []
for d in map(int, read().split()):
    while event and event[-1][0] <= d:
        time, k, x = event.pop()
        if k == 1:
            avl.insert(x, 1)
        else:
            avl.delete(x)
    x = avl.lower_bound(-INF)
    ans.append(x if x < INF else -1)

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

Submission status: Accepted

Solution code:
import sys
INF = 1 << 30


class Node:
    def __init__(self, key):
        self.key = key
        self.lch = None
        self.rch = None
        self.bias = 0


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

    def rotate_left(self, v):
        u = v.rch
        v.rch = u.lch
        u.lch = 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.lch
        v.lch = u.rch
        u.rch = 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.lch
        t = u.rch
        u.rch = t.lch
        t.lch = u
        v.lch = t.rch
        t.rch = v
        self.update_bias_double(t)
        return t

    def rotateRL(self, v):
        u = v.rch
        t = u.lch
        u.lch = t.rch
        t.rch = u
        v.rch = t.lch
        t.lch = v
        self.update_bias_double(t)
        return t

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

    def add(self, key):
        if self.root is None:
            self.root = Node(key)
            self.size += 1
            return

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

        self.size += 1

        p, pdir = history[-1]
        if pdir == 1:
            p.lch = Node(key)
        else:
            p.rch = Node(key)

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

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

            if b == 2:
                u = v.lch
                if u.bias == -1:
                    new_v = self.rotateLR(v)
                else:
                    new_v = self.rotate_right(v)
                break
            if b == -2:
                u = v.rch
                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.lch = new_v
            else:
                p.rch = new_v

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

        self.size -= 1

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

            v.key = lmax.key

            v = lmax

        c = v.rch if v.lch is None else v.lch

        if history:
            p, pdir = history[-1]
            if pdir == 1:
                p.lch = c
            else:
                p.rch = 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.lch.bias == -1:
                    new_p = self.rotateLR(p)
                else:
                    new_p = self.rotate_right(p)

            elif b == -2:
                if p.rch.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.lch = new_p
                else:
                    gp.rch = new_p
                if new_p.bias != 0:
                    break
        return True

    def lower_bound(self, key):
        ret = INF
        v = self.root
        while v is not None:
            if v.key >= key:
                if ret > v.key:
                    ret = v.key
                v = v.lch
            else:
                v = v.rch
        return ret

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
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, 0, x))

event.sort(reverse=True)

avl = AVLTree()
ans = []
for d in map(int, read().split()):
    while event and event[-1][0] <= d:
        time, k, x = event.pop()
        if k == 1:
            avl.add(x)
        else:
            avl.remove(x)
    x = avl.lower_bound(-INF)
    ans.append(x if x < INF else -1)

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

Submission status: Accepted

Solution code:
"""
愚直に一人一人交通止めに対してシミュレートしていは、絶対に間に合わない。

そこで、「この時間に出発したら"まず最初に"この通行止めで引っかかる」というのを前処理でまとめておく。
これは座標圧縮とセグメント木っぽいものを用いることで実現可能。
"""
N,Q = map(int,input().split())
STX = [list(map(int,input().split())) for _ in range(N)]
D = [int(input()) for _ in range(Q)]
times = set(D+[s-x for s,t,x in STX]+[t-x for s,t,x in STX])
compTimes = {t:i for i,t in enumerate(sorted(times))}

class originalSegTree:
    def __init__(self,n):
        self.end_leaves = 2**n.bit_length()
        self.tree = [float("INF")]*(2*self.end_leaves)
    
    def add(self,left,right,x):
        L = left + self.end_leaves
        R = right + self.end_leaves
        while L < R:
            if L&1:
                self.tree[L] = min(self.tree[L],x)
                L += 1
            if R&1:
                R -= 1
                self.tree[R] = min(self.tree[R],x)
            L >>= 1
            R >>= 1
    
    def merge(self):
        for i in range(1,self.end_leaves):
            self.tree[i*2] = min(self.tree[i],self.tree[i*2])
            self.tree[i*2+1] = min(self.tree[i],self.tree[i*2+1])

seg = originalSegTree(len(compTimes))
for s,t,x in STX:
    a = compTimes[s-x]
    b = compTimes[t-x]
    seg.add(a,b,x)

seg.merge()

for d in D:
    c = compTimes[d]
    ans = seg.tree[c+seg.end_leaves]
    if ans == float("INF"):
        ans = -1
    print(ans)

Submission status: Accepted

Solution code:
import heapq
# sys.stdin.readline()
import sys
input = sys.stdin.readline

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

S,T,X = [],[],[]

Ev = []
for _ in range(N):
  s,t,x = list(map(int, input().split())) 
  Ev.append((s-x,True,x))
  Ev.append((t-x,False,x))
"""
2 5 6
5 -1
4 2
3 3
2 4
1 5
0 -1
"""
Ev.sort()
#print(Ev)
# C++のSetはminもO(logN)で取れるが、Pythonは無理。
# setとheapqを併用すると計算量が実現できる。
h = []
closed = set()
eidx = 0
D = []

# 受け取った方が早い・・・？
for i in range(Q):
  D.append(int(input()))

for d in D:
  # dはsortedでinputされる。
  #d = int(input())
  #Query.append(d)
  while eidx < 2*N and Ev[eidx][0] <= d:
    #pop
    t,e,x = Ev[eidx]
    eidx += 1
    if e:
      heapq.heappush(h, x)
      closed.add(x)
    else:
      closed.remove(x)
      
  # heqpqの最小値がsetに含まれている間、捨て続ければ、setの要素とheapqの要素が一致する
  while h and h[0] not in closed:
    heapq.heappop(h)
    
  # assert( len(h) == len(set) )
  if h:
    print(h[0])
  else:
    print(-1)