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):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
MOD = 10 ** 9 + 7


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

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

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 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 __str__(self): return toGraph("", "", self.root).rstrip()

    
    def balanced(self): return balanced(self.root)

    
    def bstValid(self): return bstValid(self.root)

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

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

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)

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

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

def toGraph(head, bar, t):
    graph = ""
    if t != None:
        graph += toGraph(head + "    ", "／", t.rst)
        node = str(t.height)
        node += ":" + str(t.key) + ":" + str(t.value)
        graph += head + bar + node + "\n"
        graph += toGraph(head + "    ", "＼", t.lst)
    return graph




def get_min(tree):
    n = tree.root
    while n.lst is not None:
        n = n.lst
    return n.value


def main(): 
    N, Q = LI()
    STX = []
    for _ in range(N):
        STX.append(LI())
    D = []
    for _ in range(Q):
        D.append(II())
 
    events = []
    for s, t, x in STX:
        events.append((s - x, x, True))  # S-X, X, add_flag
        events.append((t - x, x, False))  # T-X, X, add_flag
 
    events.sort()  
    # D is already sorted by input.
 
    d = D.pop(0)
    d_num = 0
    ans = [-1] * Q
    m = AVLMap()
    for time, x, add_flag in events:
        while d < time:
            if not m:
                ans[d_num] = -1
                d = D.pop(0)
                d_num += 1
                continue
            else:
                while True:
                    ans[d_num] = get_min(m)
                    d = D.pop(0)
                    d_num += 1
                    break
        if add_flag:
            m.insert(x, x)
        else:
            m.delete(x)
 
    for i in ans: print(i)

main()

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
MOD = 10 ** 9 + 7
INF = 10 ** 18

from collections.abc import Sequence, Set
from bisect import bisect_left
from itertools import chain

from heapq import heappush, heappop

class HeapqSet():
    def __init__(self):
        self._set = set()
        self._list = list()

    def add(self, a):
        if a in self._set:
            return
        else:
            self._set.add(a)
            heappush(self._list, a)

    def remove(self, a):
        if a not in self._set:
            raise ValueError
        else:
            self._set.remove(a)

    def pop_min(self):
        if not self._set:
            self._list = list()
            return None
        while True:
            a = heappop(self._list)
            if a not in self._set:
                continue
            else:
                self._set.remove(a)
                break
        return a

    def peek_min(self):
        if not self._set:
            self._list = list()
            return None
        while True:
            a = self._list[0]
            if a not in self._set:
                heappop(self._list)
            else:
                break
        return a

    def is_empty(self):
        return self._set

    def __bool__(self):
        return True if self._set else False





def main(): 
    N, Q = LI()
    events = []
    for _ in range(N):
        stx = LI()
        # events.append((s - x, x, True))  # S-X, X, add_flag
        # events.append((t - x, x, False))  # T-X, X, add_flag
        events.append((stx[0] - stx[2], stx[2], True))  # S-X, X, add_flag
        events.append((stx[1] - stx[2], stx[2], False))  # T-X, X, add_flag
    for _ in range(Q):
        events.append((II(), INF, -1))
 
    events.sort(key=lambda x:x[0])  
 
    from array import array
    ans = array('i')
    
    m = HeapqSet()
    # for time, x, add_flag in events:
    change_flag = True
    min_ = INF
    for txa in events:
        if txa[2] == -1:
            if not m:
                ans.append(-1)
                # ans += '-1\n'
            else:
                if change_flag:
                    min_ = m.peek_min()
                    change_flag = False
                ans.append(min_)
                # ans += str(m[0])+'\n'
        elif txa[2]:
            m.add(txa[1])
            if txa[1] < min_:
                min_ = txa[1]
                change_flag = False
        else:
            m.remove(txa[1])
            if txa[1] == min_ and not m.is_empty():
                min_ = m.peek_min()
                change_flag = False
            elif not m:
                min_ = INF
                change_flag = False
 
    
    # print('\n'.join(map(str, ans)))
    print('\n'.join(map(str, ans.tolist())))


main()

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
MOD = 10 ** 9 + 7
INF = 10 ** 18

from collections.abc import Sequence, Set
from bisect import bisect_left
from itertools import chain

from heapq import heappush, heappop

class HeapSet():
    
    def __init__(self):
        self._set = set()
        self._list = list()

    def add(self, a):
        if a in self._set:
            return
        else:
            self._set.add(a)
            heappush(self._list, a)

    def remove(self, a):
        if a not in self._set:
            raise ValueError
        else:
            self._set.remove(a)

    def peek(self):
        if not self._set:
            self._list = list()
            raise IndexError
        while True:
            a = self._list[0]
            if a not in self._set:
                heappop(self._list)
                continue
            else:
                break
        return a

    def pop(self):
        a = self.peek()
        self._set.remove(a)
        heappop(self._list)
        return a


    def get_set(self): return self._set
    def get_heapq(self): return self._list
    def get_list(self): return self._list
    def __bool__(self): return True if self._set else False
    def __contains__(self, a): return a in self._set
    def __len__(self): return len(self._set)
    def __repr__(self): return "HeapSet(" + (repr(self._set) if self._set else '') + ")"





def main(): 
    N, Q = LI()
    events = []
    for _ in range(N):
        stx = LI()
        # events.append((s - x, x, True))  # S-X, X, add_flag
        # events.append((t - x, x, False))  # T-X, X, add_flag
        events.append((stx[0] - stx[2], stx[2], True))  # S-X, X, add_flag
        events.append((stx[1] - stx[2], stx[2], False))  # T-X, X, add_flag
    for _ in range(Q):
        events.append((II(), INF, -1))
 
    
    events.sort()  
 
    from array import array
    ans = array('i')
    
    m = HeapSet()
    # for time, x, add_flag in events:
    change_flag = True
    min_ = INF
    for txa in events:
        if txa[2] == -1:
            if not m:
                ans.append(-1)
                # ans += '-1\n'
            else:
                if change_flag:
                    min_ = m.peek()
                    change_flag = False
                ans.append(min_)
                # ans += str(m[0])+'\n'
        elif txa[2]:
            m.add(txa[1])
            if txa[1] < min_:
                min_ = txa[1]
                change_flag = False
        else:
            m.remove(txa[1])
            if txa[1] == min_ and m:
                min_ = m.peek()
                change_flag = False
            elif not m:
                min_ = INF
                change_flag = False
 
    
    # print('\n'.join(map(str, ans)))
    print('\n'.join(map(str, ans.tolist())))


main()

Verdicts: Runtime Error

Runtime Error

Accepted