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
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   # 右部分木

# 部分木 t の高さを返す
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): # ２分探索木 v の左回転。回転した木を返す
    u = v.rst; t2 = u.lst
    u.lst = v; v.rst = t2
    modHeight(u.lst)
    modHeight(u)
    return u
def rotateR(u): # ２分探索木 u の右回転。回転した木を返す
    v = u.lst; t2 = v.rst
    v.rst = u; u.lst = t2
    modHeight(v.rst)
    modHeight(v)
    return v
def rotateLR(t): # ２分探索木 t の二重回転(左回転 -> 右回転)。回転した木を返す
    t.lst = rotateL(t.lst)
    return rotateR(t)
def rotateRL(t): # ２分探索木 t の二重回転(右回転 -> 左回転)。回転した木を返す
    t.rst = rotateR(t.rst)
    return rotateL(t)

###############################################################################
# AVL木マップクラス
###############################################################################

class AVLMap:
    def __init__(self):
        self.root   = None  # AVL木の根。Node 型
        self.change = False # 修正が必要かを示すフラグ(True:必要, False:不要)
        self.lmax   = None  # 左部分木のキーの最大値
        self.value  = None  # lmax に対応する値

    ###########################################################################
    # バランス回復
    ###########################################################################

    # 挿入時の修正(balanceLi:左部分木への挿入, balanceRi:右部分木への挿入)
    def balanceLi(self, t): return self.balanceL(t)
    def balanceRi(self, t): return self.balanceR(t)

    # 削除時の修正(balanceLd:左部分木での削除, balanceRd:右部分木での削除)
    def balanceLd(self, t): return self.balanceR(t)
    def balanceRd(self, t): return self.balanceL(t)

    # 部分木 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

    # 部分木 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

    ###########################################################################
    # insert(挿入)
    ###########################################################################

    # エントリー(key, x のペア)を挿入する
    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

    ###########################################################################
    # delete(削除)
    ###########################################################################

    # key で指すエントリー(ノード)を削除する
    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)

    # 部分木 t の最大値のノードを削除する
    # 戻り値は削除により修正された部分木
    # 削除した最大値を lmax に保存する
    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 # 左部分木を昇格させる

    ###########################################################################
    # member(検索)等
    ###########################################################################

    # キーの検索。ヒットすれば True、しなければ False
    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

    # キーから値を得る。キーがヒットしない場合は None を返す
    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

    # マップが空なら True、空でないなら False
    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())

    ###########################################################################
    # Debug 用メソッド
    ###########################################################################

    # AVL木をグラフ文字列に変換する
    def __str__(self): return toGraph("", "", self.root).rstrip()

    # AVL木のバランスが取れているか確認する
    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)

###############################################################################
# Debug 用作業メソッド
###############################################################################

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()  # O(N log N)
    # 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()

Submission status: Runtime Error

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

STOP = []
for _ in range(N):
  s, t, x = map(int, input().strip().split(' '))
  tuple = (s + x, t + x, s, t, x)
  STOP.append(tuple)

COMPRESS = []
STOP = sorted(STOP)

len_stop = len(STOP)

a, b, s, t, x = STOP[0]
i = 1
while i < len_stop:
  a1, b1, s1, t1, x1 = STOP[i]
  i += 1
  if b1 <= b:
    pass
  else:
    COMPRESS.append((s, t, x))
    a = a1
    b = b1
    s = s1
    t = t1
    x = x1

COMPRESS.append((s, t, x))

D = [(i, -int(input().strip())) for i in range(Q)]

#print(STOP)
#print(COMPRESS)
RESULT = {i: -1 for i in range(len(D))}
for s, t, x in COMPRESS:
  remove_index = []
  for i, (q, d) in enumerate(D):
    if d + s <= x < d + t:
      RESULT[q] = x
      remove_index.append(i)

  for i in remove_index:
    del D[i]

for _, v in sorted(RESULT.items()):
  print(v)

Submission status: Runtime Error

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

STOP = []
for _ in range(N):
  s, t, x = map(int, input().strip().split(' '))
  STOP.append((s, t, x))

STOP = sorted(STOP)
D = [(i, -int(input().strip())) for i in range(Q)]

RESULT = {i: -1 for i in range(len(D))}
for s, t, x in STOP:
  remove_index = []
  for i, (q, d) in enumerate(D):
    if d + s <= x < d + t:
      RESULT[q] = x
      remove_index.append(i)

  for i in remove_index:
    del D[i]

for _, v in sorted(RESULT.items()):
  print(v)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
rl = lambda: list(input().split()))
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7


N,Q=rl()
TT = []
now = set()
for _ in range(N):
    s,t,x = rl()
    TT.append((s-x-0.5,1,x))
    TT.append((t-x-0.5,-1,x))
for i in range(Q):
    d = ri()
    TT.append((d,0,i))


TT.sort()
mx = INF
mx_f = False
ans = [-1]*Q
for st,w,x in TT:
    if w > 0:
        now.add(x)
        if mx > x:
            mx = x
            mx_f = True
    elif w < 0:
        now.remove(x)
        if mx == x:
            mx_f = False
    elif len(now) > 0:
        if not mx_f:
            mx = min(now)
            mx_f = True
        ans[x] = mx
print(*ans,sep='\n')

Submission status: Runtime Error

Solution code:
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   # 右部分木

# 部分木 t の高さを返す
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): # ２分探索木 v の左回転。回転した木を返す
    u = v.rst; t2 = u.lst
    u.lst = v; v.rst = t2
    modHeight(u.lst)
    modHeight(u)
    return u
def rotateR(u): # ２分探索木 u の右回転。回転した木を返す
    v = u.lst; t2 = v.rst
    v.rst = u; u.lst = t2
    modHeight(v.rst)
    modHeight(v)
    return v
def rotateLR(t): # ２分探索木 t の二重回転(左回転 -> 右回転)。回転した木を返す
    t.lst = rotateL(t.lst)
    return rotateR(t)
def rotateRL(t): # ２分探索木 t の二重回転(右回転 -> 左回転)。回転した木を返す
    t.rst = rotateR(t.rst)
    return rotateL(t)

###############################################################################
# AVL木マップクラス
###############################################################################

class AVLMap:
    def __init__(self):
        self.root   = None  # AVL木の根。Node 型
        self.change = False # 修正が必要かを示すフラグ(True:必要, False:不要)
        self.lmax   = None  # 左部分木のキーの最大値
        self.value  = None  # lmax に対応する値

    ###########################################################################
    # バランス回復
    ###########################################################################

    # 挿入時の修正(balanceLi:左部分木への挿入, balanceRi:右部分木への挿入)
    def balanceLi(self, t): return self.balanceL(t)
    def balanceRi(self, t): return self.balanceR(t)

    # 削除時の修正(balanceLd:左部分木での削除, balanceRd:右部分木での削除)
    def balanceLd(self, t): return self.balanceR(t)
    def balanceRd(self, t): return self.balanceL(t)

    # 部分木 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

    # 部分木 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

    ###########################################################################
    # insert(挿入)
    ###########################################################################

    # エントリー(key, x のペア)を挿入する
    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

    ###########################################################################
    # delete(削除)
    ###########################################################################

    # key で指すエントリー(ノード)を削除する
    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)

    # 部分木 t の最大値のノードを削除する
    # 戻り値は削除により修正された部分木
    # 削除した最大値を lmax に保存する
    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 # 左部分木を昇格させる

    ###########################################################################
    # member(検索)等
    ###########################################################################

    # キーの検索。ヒットすれば True、しなければ False
    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

    # キーから値を得る。キーがヒットしない場合は None を返す
    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

    # マップが空なら True、空でないなら False
    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())

    ###########################################################################
    # Debug 用メソッド
    ###########################################################################

    # AVL木をグラフ文字列に変換する
    def __str__(self): return toGraph("", "", self.root).rstrip()

    # AVL木のバランスが取れているか確認する
    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)

###############################################################################
# Debug 用作業メソッド
###############################################################################

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()  # O(N log N)
    # 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()

Submission status: Runtime Error

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

debug = True
#debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

class Event:
    def __repr__(self):
            return str(self.__dict__)

class User:
    def __repr__(self):
            return str(self.__dict__)

def solve():
    n, q = map(int, input().split())
    l_event = []
    for i in range(n):
        s, t, x = map(int, input().split())

        # 追加イベント
        e = Event()
        e.time = s-x
        e.type = 1 # add
        e.pos = x
        l_event.append(e)

        # 削除イベント
        e = Event()
        e.time = t-x
        e.type = -1 # delete
        e.pos = x
        l_event.append(e)

    l_user = []
    for i in range(q):
        d = int(input())

        # ユーザ評価イベント
        u = User()
        u.time = d + 0.5 # ユーザが出発する時刻までのイベントを先に処理したいので、0.5ずらす
        u.idx = i
        l_user.append(u)

    # リストを時刻でソート O(NlogN)
    l_event = sorted(l_event, key=lambda e: e.time)

    # ユーザも時刻でソート O(QlogQ)
    l_user = sorted(l_user, key=lambda e: e.time)


    ans = []
    s_stop = set()
    current_user_idx = 0

    # リストを順に処理する 全体 O(N + Qlog(2N))
    for e in l_event: # 中身が O(1) なら O(N)

        # 次処理するイベントの時刻より前のユーザをすべて処理する
        while(True): # この while 文は最大Q回しか回らないので、全体 O(Qlog(2N))
            u = l_user[current_user_idx]
            if u.time < e.time:
                if len(s_stop) != 0:
                    ans.append(min(s_stop))
                else:
                    ans.append(-1)

                current_user_idx += 1 # 次のユーザへ
                if current_user_idx >= q:  # 人の処理が終わっている場合、終わり
                    break
            else:
                # 次のイベントを処理
                break

        if e.type == 1: # add
            s_stop.add(e.pos)
        else: # delete
            s_stop.remove(e.pos)

    ans += [-1] * (q - current_user_idx)

    import numpy as np
    arg = [u.idx for u in l_user]
    ans = np.array(ans)[arg]
    for i in range(q):
        print(ans[i])

solve()

Submission status: Runtime Error

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

debug = True
#debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

class Event:
    def __repr__(self):
            return str(self.__dict__)

class User:
    def __repr__(self):
            return str(self.__dict__)

def solve():
    n, q = map(int, input().split())
    l_event = []
    for i in range(n):
        s, t, x = map(int, input().split())

        # 追加イベント
        e = Event()
        e.time = s-x
        e.type = 1 # add
        e.pos = x
        l_event.append(e)

        # 削除イベント
        e = Event()
        e.time = t-x
        e.type = -1 # delete
        e.pos = x
        l_event.append(e)

    l_user = []
    for i in range(q):
        d = int(input())

        # ユーザ評価イベント
        u = User()
        u.time = d + 0.5 # ユーザが出発する時刻までのイベントを先に処理したいので、0.5ずらす
        u.idx = i
        l_user.append(u)

    # リストを時刻でソート O(NlogN)
    l_event = sorted(l_event, key=lambda e: e.time)

    # ユーザも時刻でソート O(QlogQ)
    l_user = sorted(l_user, key=lambda e: e.time)


    ans = {i:-1 for i in range(q)} # 答えの配列
    s_stop = set()
    current_user_idx = 0

    # リストを順に処理する 全体 O(N + Qlog(2N))
    for e in l_event: # 中身が O(1) なら O(N)

        # 次処理するイベントの時刻より前のユーザをすべて処理する
        while(True): # この while 文は最大Q回しか回らないので、全体 O(Qlog(2N))
            u = l_user[current_user_idx]
            if u.time < e.time:
                if len(s_stop) != 0:
                    ans[u.idx] = min(s_stop)

                current_user_idx += 1 # 次のユーザへ
                if current_user_idx >= len(l_user):  # 人の処理が終わっている場合、終わり
                    break
            else:
                break

        if e.type == 1: # add
            s_stop.add(e.pos)
        else: # delete
            s_stop.remove(e.pos)

    for i in range(q):
        print(ans[i])

solve()

Submission status: Runtime Error

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

class Event:
    def __repr__(self):
            return str(self.__dict__)

class User:
    def __repr__(self):
            return str(self.__dict__)

def solve():
    n, q = map(int, input().split())
    l_event = []
    for i in range(n):
        s, t, x = map(int, input().split())

        # 追加イベント
        e = Event()
        e.time = s-x
        e.type = 1 # add
        e.pos = x
        l_event.append(e)

        # 削除イベント
        e = Event()
        e.time = t-x
        e.type = -1 # delete
        e.pos = x
        l_event.append(e)

    l_user = []
    for i in range(q):
        d = int(input())

        # ユーザ評価イベント
        u = User()
        u.time = d + 0.5 # ユーザが出発する時刻までのイベントを先に処理したいので、0.5ずらす
        u.idx = i
        l_user.append(u)

    # リストを時刻でソート O(NlogN)
    l_event = sorted(l_event, key=lambda e: e.time)

    # ユーザも時刻でソート O(QlogQ)
    l_user = sorted(l_user, key=lambda e: e.time)

    ans = [-1]*q # 答えの配列
    s_stop = set()
    minstop = 10**9 + 1

    current_user_idx = 0

    # リストを順に処理する 全体 O(N + Qlog(2N))
    for e in l_event: # 中身が O(1) なら O(N)


        # 次処理するイベントの時刻より前のユーザをすべて処理する
        while(True): # この while 文は最大Q回しか回らないので、全体 O(Qlog(2N))
            u = l_user[current_user_idx]
            if u.time < e.time:
                if len(s_stop) != 0:
                    if minstop == -1 or minstop == 10**9 + 1:
                        minstop = min(s_stop) # O(log(2N))
                    ans[u.idx] = minstop

                current_user_idx += 1 # 次のユーザへ
                if current_user_idx >= len(l_user):  # 人の処理が終わっている場合、終わり
                    break
            else:
                break

        if e.type == 1: # add
            s_stop.add(e.pos)
            if minstop > e.pos:
                e.pos = minstop # update minstop in advance

        else: # delete
            s_stop.remove(e.pos)
            if minstop == e.pos:
                minstop = -1 # unknown

    print("\n".join([str(a) for a in ans]))

solve()

Submission status: Runtime Error

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

class Event:
    def __repr__(self):
            return str(self.__dict__)

class User:
    def __repr__(self):
            return str(self.__dict__)

def solve():
    n, q = map(int, input().split())
    l_event = []
    for i in range(n):
        s, t, x = map(int, input().split())

        # 追加イベント
        e = Event()
        e.time = s-x
        e.type = 1 # add
        e.pos = x
        l_event.append(e)

        # 削除イベント
        e = Event()
        e.time = t-x
        e.type = -1 # delete
        e.pos = x
        l_event.append(e)

    l_user = []
    for i in range(q):
        d = int(input())

        # ユーザ評価イベント
        u = User()
        u.time = d + 0.5 # ユーザが出発する時刻までのイベントを先に処理したいので、0.5ずらす
        u.idx = i
        l_user.append(u)

    # リストを時刻でソート O(NlogN)
    l_event = sorted(l_event, key=lambda e: e.time)

    # ユーザも時刻でソート O(QlogQ)
    l_user = sorted(l_user, key=lambda e: e.time)

    ans = [-1]*q # 答えの配列
    s_stop = set()

    current_user_idx = 0

    # リストを順に処理する
    for e in l_event: #O(N+Q)

        # 次処理するイベントの時刻より前のユーザをすべて処理する
        while(True):
            u = l_user[current_user_idx]
            if u.time < e.time:
                if len(s_stop) != 0:
                    ans[u.idx] = min(s_stop)
                current_user_idx += 1
            else:
                break

        if e.type == 1: # add
            s_stop.add(e.pos)
        else: # delete
            s_stop.remove(e.pos)

    print("\n".join([str(a) for a in ans]))

solve()

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
STX = [[int(_) for _ in input().split()] for _ in range(N)]
STX = sorted(STX, key=lambda x:-x[2])
D = [int(input()) for _ in range(Q)]
ans = [-1]*(10**6 + 1)

for i in STX:
    X = i[2]
    S = X - i[1] + 1
    G = X - i[0]
    if S > 0:
        continue
    elif G > 0:
        G = 0
    
    ans[-G:-S+1] = [X] * (G-S+1)

for i in D:
    print(ans[i])

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
STX = [[int(_) for _ in input().split()] for _ in range(N)]
STX = sorted(STX, key=lambda x:-x[2])
D = [int(input()) for _ in range(Q)]
ans = [-1]*(10**9 + 1)

for i in STX:
    X = i[2]
    S = X - i[1] + 1
    G = X - i[0]
    if S > 0:
        continue
    elif G > 0:
        G = 0
    
    ans[-G:-S+1] = [X] * (G-S+1)

for i in D:
    print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
STX = [[int(_) for _ in input().split()] for _ in range(N)]
STX = sorted(STX, key=lambda x:-x[2])
D = [int(input()) for _ in range(Q)]
ans = [-1]*(10**9 + 1)

for i in STX:
    X = i[2]
    S = X - i[1] + 1
    G = X - i[0]
    if S > 0:
        continue
    elif G > 0:
        G = 0
    
    ans[-G:-S+1] = [X] * (G-S+1)

for i in D:
    print(ans[i])