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 .

Solution (Python):
class AVLtree:
    """
    参考：http://www.nct9.ne.jp/m_hiroi/light/pyalgo12.html
    insert : 挿入
    erase : 削除
    lower_bound(x) : x <= v なる最小のv、なければ-float("inf")、最小値はlower(-float("inf"))
    upper_bound(x) : v < x なる最大のv、なければfloat("inf")、最大値はupper(float("inf"))
    print(avltree) : デバッグ用
    """
 
    def __init__(self):
        self.root = None

        
    def insert(self, x):
        if self.root is None:
            self.root = Node(x)
            return
        q = []
        node = self.root
        while True:
            if node.val == x:
                return
            elif x < node.val:
                q.append((node, 0))
                if node.left is None:
                    node.left = Node(x)
                    break
                node = node.left
            else:
                q.append((node, 1))
                if node.right is None:
                    node.right = Node(x)
                    break
                node = node.right
                
        
        new_node = None
        while q:
            node, key = q.pop()
            if not key:
                node.bal += 1
            else:
                node.bal -= 1
            bal = node.bal
            if not bal:
                return
            if bal == 2:
                if node.left.bal == -1:
                    node.left = node.left._rotateL()
                    new_node = node._rotateR()
                    new_node._update_bal()
                else:
                    new_node = node._rotateR()
                    new_node.bal = 0
                    node.bal = 0
                break
            elif bal == -2:
                if node.right.bal == 1:
                    node.right = node.right._rotateR()
                    new_node = node._rotateL()
                    new_node._update_bal()
                else:
                    new_node = node._rotateL()
                    new_node.bal = 0
                    node.bal = 0
                break
        if q:
            node, key = q.pop()
            if not key:
                node.left = new_node
            else:
                node.right = new_node
        elif new_node is not None:
            self.root = new_node

            
    def erase(self, x):
        if self.root is None:
            return
        q = []
        node = self.root
        while node is not None:
            if node.val == x:
                break
            if x < node.val:
                q.append((node, 0))
                node = node.left
            else:
                q.append((node, 1))
                node = node.right
        else:
            return
        if node.left is not None and node.right is not None:
            q.append((node, 1))
            min_node = node.right
            while min_node.left is not None:
                q.append((min_node, 0))
                min_node = min_node.left
            node.val = min_node.val
            node = min_node
        if q:
            pre, key = q[-1]
        else:
            pre = None
        if node.left is None:
            cnode = node.right
        else:
            cnode = node.left
        if pre is None:
            self.root = cnode
            return
        if not key:
            pre.left = cnode
        else:
            pre.right = cnode
        
        
        while q:
            new_node = None
            node, key = q.pop()
            if not key:
                node.bal -= 1
            else:
                node.bal += 1
            bal = node.bal
            if bal == 2:
                if node.left.bal == -1:
                    node.left = node.left._rotateL()
                    new_node = node._rotateR()
                    new_node._update_bal()
                else:
                    new_node = node._rotateR()
                    if not new_node.bal:
                        new_node.bal = -1
                        node.bal = 1
                    else:
                        new_node.bal = 0
                        node.bal = 0
            elif bal == -2:
                if node.right.bal == 1:
                    node.right = node.right._rotateR()
                    new_node = node._rotateL()
                    new_node._update_bal()
                else:
                    new_node = node._rotateL()
                    if not new_node.bal:
                        new_node.bal = 1
                        node.bal = -1
                    else:
                        new_node.bal= 0
                        node.bal = 0
            elif bal:
                break
            if new_node is not None:
                if not q:
                    self.root = new_node
                    return
                node, key = q[-1]
                if not key:
                    node.left = new_node
                else:
                    node.right = new_node
                if new_node.bal:
                    break

                    
    def lower_bound(self, x):
        res = float("inf")
        node = self.root
        while node is not None:
            if x <= node.val:
                res = node.val
                node = node.left
            else:
                node = node.right
        return res
    
    
    def upper_bound(self, x):
        res = -float("inf")
        node = self.root
        while node is not None:
            if x <= node.val:
                node = node.left
            else:
                res = node.val
                node = node.right
        return res
    
    
    def __str__(self):
        if self.root is None:
            return "[]"
        buff = "["
        for x in self.root._dfs():
            buff += str(x)+", "
        buff = buff.rstrip(", ")
        buff += "]"
        return buff


class Node:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.bal = 0 
    
    
    def _rotateR(self):
        nodeL = self.left
        self.left = nodeL.right
        nodeL.right = self
        return nodeL
    
    
    def _rotateL(self):
        nodeR = self.right
        self.right = nodeR.left
        nodeR.left = self
        return nodeR
    
    
    def _update_bal(self):
        if self.bal == 1:
            self.right.bal = -1
            self.left.bal = 0
        elif self.bal == -1:
            self.right.bal = 0
            self.left.bal = 1
        else:
            self.right.bal = 0
            self.left.bal = 0
        self.bal = 0
    
    
    def _dfs(self):
        if self is not None:
            if self.left is not None:
                for x in self.left._dfs():
                    yield x
            yield self.val
            if self.right is not None:
                for x in self.right._dfs():
                    yield x

n,q = map(int, input().split())
stx = [list(map(int, input().split())) for _ in range(n)]
e = [(s-x,x+i/n,i) for i,(s,_,x) in enumerate(stx)]+[(t-x,x+i/n,i) for i,(_,t,x) in enumerate(stx)]
e.sort(key = lambda x:x[0])
D = [int(input()) for _ in range(q)]
avl = AVLtree()
ans = []
f = [0]*n
j = 0
N = 2*n
for d in D:
  while j < N and e[j][0] <= d:
    _,x,i = e[j]
    if f[i]:
      avl.erase(x)
    else:
      avl.insert(x)
      f[i] = 1
    j += 1
  m = avl.lower_bound(-float("inf"))
  ans.append(int(m) if m != float("inf") else -1)

for i in ans:
  print(i)

Solution (Python):
from heapq import heappop,heappush
from collections import defaultdict
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,2,x))

for i in range(Q):
    d = int(input())
    event.append((d,3,i))
event.sort()

memo = defaultdict(int)
nowStop = []
ans = [-1]*Q
for t,e,x in event:
    if e == 1:
        heappush(nowStop,x)
        memo[x] += 1
    if e == 2:
        memo[x] -= 1
    if e == 3:
        while nowStop:
            s = nowStop[0]
            if memo[s] == 0:
                heappop(nowStop)
            else:
                ans[x] = s
                break
for a in ans:
    print(a)

Solution (Python):
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

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


        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

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

Solution (Python):
import sys
INF = 1 << 30


class Node:
    __slots__ = ["key", "val", "lch", "rch", "bias"]
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.lch = None
        self.rch = None
        self.bias = 0


class AVLTree:
    __slots__ = ["root"]
    def __init__(self):
        self.root = None

    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 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.lch
            elif v.key < key:
                history.append((v, -1))
                v = v.rch
            elif v.key == key:
                v.val = val
                return

        p, pdir = history[-1]
        if pdir == 1:
            p.lch = Node(key, val)
        else:
            p.rch = 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.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 delete(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

        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.val = lmax.val

            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 get(self, key):
        v = self.root
        while v is not None:
            if key < v.key:
                v = v.lch
            elif v.key < key:
                v = v.rch
            else:
                return v.val
        return None

    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

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

Solution (Python):
import sys
INF = 1 << 30


class Node:
    __slots__ = ["key", "val", "lch", "rch", "bias"]
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.lch = None
        self.rch = None
        self.bias = 0


class AVLTree:
    __slots__ = ["root"]
    def __init__(self):
        self.root = None

    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 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.lch
            elif v.key < key:
                history.append((v, -1))
                v = v.rch
            elif v.key == key:
                v.val = val
                return

        p, pdir = history[-1]
        if pdir == 1:
            p.lch = Node(key, val)
        else:
            p.rch = 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.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 delete(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

        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.val = lmax.val

            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 get(self, key):
        v = self.root
        while v is not None:
            if key < v.key:
                v = v.lch
            elif v.key < key:
                v = v.rch
            else:
                return v.val
        return None

    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

    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[x] = 1
        else:
            del avl[x]
    x = avl.lower_bound(-INF)
    ans.append(x if x < INF else -1)

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