Problem: 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.

Submission attempts (in order):
class Node: 
    def __init__(self, height, key, x):
        self.height = height 
        self.key    = key    
        self.value  = x      
        self.lst    = None   
        self.rst    = None   


def height(t): return 0 if t is None else t.height


def bias(t): return height(t.lst) - height(t.rst)


def modHeight(t): t.height = 1 + max(height(t.lst), height(t.rst))

def rotateL(v): 
    u = v.rst; t2 = u.lst
    u.lst = v; v.rst = t2
    modHeight(u.lst)
    modHeight(u)
    return u
def rotateR(u): 
    v = u.lst; t2 = v.rst
    v.rst = u; u.lst = t2
    modHeight(v.rst)
    modHeight(v)
    return v
def rotateLR(t): 
    t.lst = rotateL(t.lst)
    return rotateR(t)
def rotateRL(t): 
    t.rst = rotateR(t.rst)
    return rotateL(t)

class AVLMap:
    def __init__(self):
        self.root   = None  
        self.change = False 
        self.lmax   = None  のキーの最大値
        self.value  = None  

    ###########################################################################
    
    ###########################################################################

    
    def balanceLi(self, t): return self.balanceL(t)
    def balanceRi(self, t): return self.balanceR(t)

    
    def balanceLd(self, t): return self.balanceR(t)
    def balanceRd(self, t): return self.balanceL(t)

    
    への挿入に伴うAVL木の修正
    での削除に伴うAVL木の修正
    def balanceL(self, t):
        if not self.change: return t
        h = height(t)
        if bias(t) == 2:
            if bias(t.lst) >= 0:
                t = rotateR(t)
            else:
                t = rotateLR(t)
        else: modHeight(t)
        self.change = (h != height(t))
        return t

    
    への挿入に伴うAVL木の修正
    での削除に伴うAVL木の修正
    def balanceR(self, t):
        if not self.change: return t
        h = height(t)
        if bias(t) == -2:
            if bias(t.rst) <= 0:
                t = rotateL(t)
            else:
                t = rotateRL(t)
        else: modHeight(t)
        self.change = (h != height(t))
        return t

    ###########################################################################
    
    ###########################################################################

    
    def insert(self, key, x): self.root = self.insert_sub(self.root, key, x)

    def insert_sub(self, t, key, x):
        if t is None:
            self.change = True
            return Node(1, key, x)
        elif key < t.key:
            t.lst = self.insert_sub(t.lst, key, x)
            return self.balanceLi(t)
        elif key > t.key:
            t.rst = self.insert_sub(t.rst, key, x)
            return self.balanceRi(t)
        else:
            self.change = False
            t.value = x
            return t

    ###########################################################################
    
    ###########################################################################

    
    def delete(self, key): self.root = self.delete_sub(self.root, key)

    def delete_sub(self, t, key):
        if t is None:
            self.change = False
            return None
        elif key < t.key:
            t.lst = self.delete_sub(t.lst, key)
            return self.balanceLd(t)
        elif key > t.key:
            t.rst = self.delete_sub(t.rst, key)
            return self.balanceRd(t)
        else:
            if t.lst is None:
                self.change = True
                return t.rst を昇格させる
            else:
                t.lst = self.delete_max(t.lst) の最大値を削除する
                t.key = self.lmax の削除した最大値で置き換える
                t.value = self.value
                return self.balanceLd(t)

    
    
    
    def delete_max(self, t):
        if t.rst is not None:
            t.rst = self.delete_max(t.rst)
            return self.balanceRd(t)
        else:
            self.change = True
            self.lmax = t.key 
            self.value = t.value
            return t.lst を昇格させる

    ###########################################################################
    
    ###########################################################################

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

    
    def lookup(self, key):
        t = self.root
        while t is not None:
            if key < t.key:
                t = t.lst
            elif key > t.key:
                t = t.rst
            else:
                return t.value
        return None

    def getmin(self):
        t = self.root
        while t is not None:
            ans = t.key
            t = t.lst
        return ans

    
    def isEmpty(self): return self.root is None

    
    def clear(self): self.root = None

    
    def keys(self): return keys_sub(self.root)

    
    def values(self): return values_sub(self.root)

    
    def items(self): return items_sub(self.root)

    
    def size(self): return len(self.keys())

    def __contains__(self, key): self.member(key)
    def __getitem__(self, key): return self.lookup(key)
    def __setitem__(self, key, x): return self.insert(key, x)
    def __delitem__(self, key): self.delete(key)
    def __bool__(self): return not self.isEmpty()
    def __len__(self): return self.size()
    def __iter__(self): return iter(self.keys())

###############################################################################

###############################################################################

def keys_sub(t):
    if t is None: return []
    return keys_sub(t.lst) + [t.key] + keys_sub(t.rst)

def values_sub(t):
    if t is None: return []
    return values_sub(t.lst) + [t.value] + values_sub(t.rst)

def items_sub(t):
    if t is None: return []
    return items_sub(t.lst) + [(t.key, t.value)] + items_sub(t.rst)

mx = 10**9 + 1

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, q = map(int, input().split())
event = []
for _ in range(n):
    s, t, x = map(int, input().split())
    event.append((s - x - 0.5, 1, x))
    event.append((t - x - 0.5, -1, x))
for i in range(q):
    event.append((int(input()), 0, i))

event.sort()

# stop = set()
stop = AVLMap()
ans = {}
for t, e, x in event:
    if e > 0:
        stop.insert(x, 0)
    elif e < 0:
        stop.delete(x)
    else:
        if stop.size() != 0:
            ans[x] = stop.getmin()
        else:
            ans[x] = -1
for i in range(q):
    print(ans[i])


import 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-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

Verdicts: Time Limit Exceeded

Accepted