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: Time Limit Exceeded

Solution code:
from bisect import bisect_left

N,Q = map(int, input().split())
STX = []
for i in range(N):
  *stx, = list(map(int, input().split()))
  STX.append(stx)
D = []
for i in range(Q):
  D.append(int(input()))

STX = sorted(STX, key=lambda x: x[2])

DI = [i for i in range(Q)]
ANS = [-1]*Q
for (s,t,x) in STX:
  s2 = (s - x)
  t2 = (t - x)

  D_sub = [D[di] for di in DI]
  start = bisect_left(D_sub, s2)
  end = bisect_left(D_sub, t2, lo=start)
    
  #print(start, end, DI)
  DI_copy = DI[:]
  while (start < end):
    di = DI_copy[start]
    ANS[di] = x
    DI.remove(di)
    start += 1

print(*ANS, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
STX = []
for i in range(N):
  *stx, = list(map(int, input().split()))
  STX.append(stx)
D = []
for i in range(Q):
  D.append(int(input()))

STX = sorted(STX, key=lambda x: x[2])

DI = [i for i in range(Q)]
ANS = [-1]*Q
for (s,t,x) in STX:
  s2 = (s - x)
  t2 = (t - x)
  for di in DI[:]:
    if ((s2 <= D[di]) and (D[di] < t2)):
      ANS[di] = x
      DI.remove(di)

print(*ANS, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from math import ceil, log2
import sys


class SegmentTree:
    def __init__(self, length, init_value=None, aggfunc=min):
        self.aggfunc = aggfunc
        self.depth = ceil(log2(length))
        self.data = [init_value] * (2 ** (1 + self.depth) - 1)
        self.origin = 2 ** self.depth - 1

    def update(self, idx, value):
        i = idx + self.origin
        self.data[i] = value
        while i > 0:
            i = (i - 1) // 2
            new_value = self.aggfunc(self.data[i * 2 + 1], self.data[i * 2 + 2])
            if self.data[i] != new_value:
                self.data[i] = new_value
            else:
                break


input = sys.stdin.readline
n, q = map(int, input().split())
stx = [tuple(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

xs = set()
events = []

for s, t, x in stx:
    events.append((s - x, 1, x))
    events.append((t - x, -1, x))
    xs.add(x)
events.sort()

xs = list(xs)
xs.sort()


zaatsu = dict(zip(xs, range(len(xs))))

ub = 10 ** 9 + 1
koujichu = SegmentTree(len(zaatsu), ub, min)

i = 0
for di in d:
    while i < len(events) and events[i][0] <= di:
        if events[i][1] == 1:
            koujichu.update(zaatsu[events[i][2]], events[i][2])
        else:
            koujichu.update(zaatsu[events[i][2]], ub)
        i += 1
    if koujichu.data[0] != ub:
        print(koujichu.data[0])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil, log2


class SegmentTree:
    def __init__(self, length, init_value=None, aggfunc=min):
        self.aggfunc = aggfunc
        self.depth = ceil(log2(length))
        self.data = [init_value] * (2 ** (1 + self.depth) - 1)
        self.origin = 2 ** self.depth - 1

    def update(self, idx, value):
        i = idx + self.origin
        self.data[i] = value
        while i > 0:
            i = (i - 1) // 2
            new_value = self.aggfunc(self.data[i * 2 + 1], self.data[i * 2 + 2])
            if self.data[i] != new_value:
                self.data[i] = new_value
            else:
                break


n, q = map(int, input().split())
stx = [tuple(map(int, input().split())) for _ in range(n)]
d = [int(input()) for _ in range(q)]

xs = set()
events = []

for s, t, x in stx:
    events.append((s - x, 1, x))
    events.append((t - x, -1, x))
    xs.add(x)
events.sort()

xs = list(xs)
xs.sort()


zaatsu = dict(zip(xs, range(len(xs))))

ub = 10 ** 9 + 1
koujichu = SegmentTree(len(zaatsu), ub, min)

i = 0
for di in d:
    while i < len(events) and events[i][0] <= di:
        if events[i][1] == 1:
            koujichu.update(zaatsu[events[i][2]], events[i][2])
        else:
            koujichu.update(zaatsu[events[i][2]], ub)
        i += 1
    if koujichu.data[0] != ub:
        print(koujichu.data[0])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil, log2


class SegmentTree:
    def __init__(self, length, init_value=None, aggfunc=min):
        self.aggfunc = aggfunc
        self.depth = ceil(log2(length))
        self.data = [init_value] * (2 ** (1 + self.depth) - 1)
        self.origin = 2 ** self.depth - 1

    def update(self, idx, value):
        i = idx + self.origin
        self.data[i] = value
        while i > 0:
            i = (i - 1) // 2
            new_value = self.aggfunc(self.data[i * 2 + 1], self.data[i * 2 + 2])
            if self.data[i] != new_value:
                self.data[i] = new_value
            else:
                break


n, q = map(int, input().split())
stx = [map(int, input().split()) for _ in range(n)]
d = [int(input()) for _ in range(q)]
xs = set()
events = []

for s, t, x in stx:
    events.append((s - x, 1, x))
    events.append((t - x, -1, x))
    xs.add(x)
events.sort()

xs = list(xs)
xs.sort()


zaatsu = dict(zip(xs, range(len(xs))))

ub = 10 ** 9 + 1
koujichu = SegmentTree(len(zaatsu), ub, min)

i = 0
for di in d:
    while i < len(events) and events[i][0] <= di:
        if events[i][1] == 1:
            koujichu.update(zaatsu[events[i][2]], events[i][2])
        else:
            koujichu.update(zaatsu[events[i][2]], ub)
        i += 1
    if koujichu.data[0] != ub:
        print(koujichu.data[0])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil, log2


class SegmentTree:
    def __init__(self, length, init_value=None, aggfunc=min):
        self.aggfunc = aggfunc
        self.depth = ceil(log2(length))
        self.data = [init_value] * (2 ** (1 + self.depth) - 1)
        self.origin = 2 ** self.depth - 1

    def update(self, idx, value):
        i = idx + self.origin
        self.data[i] = value
        while i > 0:
            i = (i - 1) // 2
            self.data[i] = self.aggfunc(self.data[i * 2 + 1], self.data[i * 2 + 2])


n, q = map(int, input().split())
stx = [map(int, input().split()) for _ in range(n)]
d = [int(input()) for _ in range(q)]
xs = set()
events = []

for s, t, x in stx:
    events.append((s - x, 1, x))
    events.append((t - x, -1, x))
    xs.add(x)
events.sort()

xs = list(xs)
xs.sort()


zaatsu = dict(zip(xs, range(len(xs))))

ub = 10 ** 9 + 1
koujichu = SegmentTree(len(zaatsu), ub, min)

i = 0
for di in d:
    while i < len(events) and events[i][0] <= di:
        if events[i][1] == 1:
            koujichu.update(zaatsu[events[i][2]], events[i][2])
        else:
            koujichu.update(zaatsu[events[i][2]], ub)
        i += 1
    if koujichu.data[0] != ub:
        print(koujichu.data[0])
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
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)

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

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

    # マップが空なら 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())

###############################################################################
# 作業メソッド
###############################################################################

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

Submission status: Time Limit Exceeded

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

ans = {}
for t, e, x in event:
    if e > 0:
        stop.add(x)
    elif e < 0:
        stop.remove(x)
    else:
        if len(stop) != 0:
            ans[x] = min(stop)
        else:
            ans[x] = -1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import bisect
N,Q = (int(x) for x in input().split())

stop_arr = []
for _ in range(N):
    S,T,X = (int(x) for x in input().split())
    stop_arr.append((S,T,X))
Q_arr = []
for _ in range(Q):
    Q_arr.append(int(input()))

stop_arr.sort(key=lambda x:x[2], reverse=True)

ans_arr = [-1]*Q

for s,t,x in stop_arr:
    q_start = bisect.bisect_left(Q_arr, s-x)
    q_stop = bisect.bisect_left(Q_arr, t-x)
    for i in range(q_start, q_stop):
        ans_arr[i] = x

for a in ans_arr:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
data=[tuple(map(int,input().split())) for i in range(N)]
stop=[(s-x,t-x,x) for s,t,x in data]
D=[int(input()) for i in range(Q)]
inf=float('inf')
L=1
while Q>L:
    L*=2
K=2*L-1
seg=[inf]*K
import bisect
def renew(b,e,k,l,r,x):
    if e<0 or b>=L:
        return
    global seg
    if k>0:
        seg[k]=min(seg[k],seg[(k-1)//2])
    if r<b or e<l:
        return
    if b<=l and r<=e:
        seg[k]=min(seg[k],x)
        return
    elif k<K-L:
        renew(b,e,2*k+1,l,(l+r)//2,x)
        renew(b,e,2*k+2,(l+r)//2,r,x)
    return 
for s,t,x in stop:
    b=bisect.bisect_left(D,s)
    e=bisect.bisect_left(D,t)
    renew(b,e,0,0,L,x)
for k in range(K-L):
    seg[2*k+1]=min(seg[2*k+1],seg[k])
    seg[2*k+2]=min(seg[2*k+2],seg[k])
for i in range(Q):
    now=i
    ans=inf
    while now>0:
        ans=min(ans,seg[now])
        now=(now-1)//2
    if seg[K-L+i]>10**19:
        print(-1)
    else:
        print(seg[K-L+i])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
data=[tuple(map(int,input().split())) for i in range(N)]
stop=[(s-x,t-x,x) for s,t,x in data]
D=[int(input()) for i in range(Q)]
inf=float('inf')
L=1
while Q>L:
    L*=2
K=2*L-1
seg=[inf]*K
import bisect
def renew(b,e,k,l,r,x):
    global seg
    if k>0:
        seg[k]=min(seg[k],seg[(k-1)//2])
    if b<=l and r<=e:
        seg[k]=min(seg[k],x)
        return
    elif k<K-L:
        renew(b,e,2*k+1,l,(l+r)//2,x)
        renew(b,e,2*k+2,(l+r)//2,r,x)
    return 
for s,t,x in stop:
    b=bisect.bisect_left(D,s)
    e=bisect.bisect_left(D,t)
    renew(b,e,0,0,L,x)
for k in range(K-L):
    seg[2*k+1]=min(seg[2*k+1],seg[k])
    seg[2*k+2]=min(seg[2*k+2],seg[k])
for i in range(Q):
    now=i
    ans=inf
    while now>0:
        ans=min(ans,seg[now])
        now=(now-1)//2
    if seg[K-L+i]>10**19:
        print(-1)
    else:
        print(seg[K-L+i])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
data=[tuple(map(int,input().split())) for i in range(N)]
stop=[(s-x,t-x,x) for s,t,x in data]
D=[int(input()) for i in range(Q)]
inf=float('inf')
L=1
while Q>L:
    L*=2
K=2*L-1
seg=[inf]*K
import bisect
def renew(b,e,k,l,r,x):
    global seg
    if k>0:
        seg[k]=min(seg[k],seg[(k-1)//2])
    if b<=l and r<=e:
        seg[k]=min(seg[k],x)
    elif k<K-L:
        renew(b,e,2*k+1,l,(l+r)//2,x)
        renew(b,e,2*k+2,(l+r)//2,r,x)
for s,t,x in stop:
    b=bisect.bisect_left(D,s)
    e=bisect.bisect_left(D,t)
    renew(b,e,0,0,L,x)
for k in range(K-L):
    seg[2*k+1]=min(seg[2*k+1],seg[k])
    seg[2*k+2]=min(seg[2*k+2],seg[k])
for i in range(Q):
    if seg[K-L+i]>10**19:
        print(-1)
    else:
        print(seg[K-L+i])

Submission status: Time Limit Exceeded

Solution code:
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,-1,x])
event=sorted(event,key=lambda x:x[0])
event.append([10**10,1,10**10])
pos=[int(input()) for _ in range(q)]
sx=set()
cnt=0
m=10**10
ans=[]
for p in pos:
  while event[cnt][0]<=p:
    s,f,x=event[cnt]
    cnt+=1
    if f==1:
      sx.add(x)
      m=min(m,x)
    else:
      sx.remove(x)
      if m==x:
        if len(sx)==0:
          m=10**10
        else:
          m=min(sx)
  if sx:
    ans.append(m)
  else:
    ans.append(-1)
for i in ans:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
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,-1,x])
event=sorted(event,key=lambda x:x[0])
event.append([10**10,1,10**10])
pos=[int(input()) for _ in range(q)]
sx=set()
cnt=0
m=10**10
ans=[]
for p in pos:
  while event[cnt][0]<=p:
    s,f,x=event[cnt]
    cnt+=1
    if f==1:
      sx.add(x)
      m=min(m,x)
    else:
      sx.remove(x)
      if m==x:
        if len(sx)==0:
          m=10**10
        else:
          m=min(list(sx))
  if len(sx)==0:
    ans.append(-1)
  else:
    ans.append(m)
for i in ans:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 16:58:00 2019

@author: YudNK
"""
import bisect as bs

N, Q = map(int, input().split())
E = []
for i in range(N):
    s, t, x = map(int, input().split())
    a = [s - x, t - x, x] #イベント
    E.append(a)
E.sort(key = lambda x: x[2])
D = []
for i in range(Q):
    D.append(int(input()))

ans = [-1]*Q

for e in E:
    l = bs.bisect_left(D, e[0])
    r = bs.bisect_left(D, e[1])
    for i in range(l, r):
        if ans[i] == -1:
            ans[i] = e[2]
        else:
            pass
    
[print(i) for i in ans]

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 16:58:00 2019

@author: YudNK
"""
#import heapq as hp
#import bisect as bs

N, Q = map(int, input().split())
E = []
for i in range(N):
    s, t, x = map(int, input().split())
    app = [s - x, -1, x] #追加イベント
    rem = [t - x, -2, x] #削除イベント
    E.append(app)
    E.append(rem)
for i in range(Q):
    d = [int(input()), i, -1]
    E.append(d)
E.sort(key = lambda x:x[0])

ans = []
stopX = []

for e in E:
    if e[1] == -1:
        stopX.append(e[2])
    elif e[1] == -2:
        stopX.remove(e[2])
    else:
        if len(stopX) != 0:
            ans.append(min(stopX))
        else:
            ans.append(-1)
[print(i) for i in ans]

Submission status: Time Limit Exceeded

Solution code:
###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, Q = mi()

Events = []
#イベントを格納する配列
#各要素はタプルで、(s-x or t-x, 1or-1, x)が入っている
#意味は、「時間s-xもしくはt-xに出発する人が」「座標xで」
# 「1:通行止めにぶつかる -1:通行止めにぶつかりそうだったが、助かる」を表す

for _ in range(N):
  s, t, x = mi()
  #1つめの要素がマイナスになることはないので、max(0, hoge)をとる。
  #どちらもマイナスといったコーナーケースでも、「0で通行止めになり0で解除される」となってから時間0に出発する人が処理されるので、影響は出ない
#……と思っていたけど、0になるイベントが複数あると、集合への出し入れがおかしくなる（0を複数入れたあと複数回だそうとするから、無いキーを出そうとしてしまう）
#時間がマイナスでもコード上全く問題無いんだから、外した！
  Events.append((s-x, 1, x))
  Events.append((t-x, -1, x))

#イベント配列は「影響を受ける人（の出発時間）」で降順ソートする
#降順ソートなので、pop()でとっていく
from operator import itemgetter
Events = sorted(Events, key=lambda x:(-x[0],-x[1]))
#発生タイミング（x[0]）が同じイベントは、集合からのout→inでも並び替える（x[1]について降順）。
#outより先にinが行われると、集合操作がおかしくなる

#イベント配列ができたので、今度は各人について処理していく
#出力する答えはAnss配列に入れていき、最後にfor文で一気に出力する
Anss = []

#制約より、Diは最初から昇順ソートされている
Ds = [int(input()) for _ in range(Q)]

nowkeptout = set() #今通行止めになっている座標を格納するset。常に昇順ソートする
nextevent = Events.pop()  #次に見るイベント
minstop = 10**9+1
for d in Ds:
  #各ループにおいて、「未処理の人のうち、最も出発時間が早い人」がdに入る
  #ということは、時間dまでのEventsを全て処理すれば、その人がぶつかる場所が分かる
  while nextevent[0]<=d: #dを越えたら止まるし、イベントがなくなっても番兵で止まる
    a, b, c = nextevent
    if b==1: #座標xが通行止めになる
      nowkeptout.add(c)
      minstop = min(c, minstop)
    else: #座標xの通行止めが解除される
      nowkeptout.remove(c)
      if c==minstop and nowkeptout: minstop = min(nowkeptout)
      elif not nowkeptout: minstop = 10**9+1
    try: nextevent = Events.pop()
    except:
      nextevent = (10**9+1, 1, 1) #要素がなくなったらもう処理が起きないようにする
      break
  #この時点で、nowkeptoutに値が入っている場合も、入っていない場合もある
  #値が入っていれば、dはその最小値の座標で通行止めにぶつかる
  #値が入っていなければ歩き続けるので、-1にする
  if nowkeptout: Anss.append(minstop)
  else: Anss.append(-1)

for ans in Anss:
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
events = []
for stx in STX:
    s, t, x = stx
    events += [[s - x, 1, x], [t - x, 0, x]]
for i in range(Q):
    events += [[D[i], 2, i]]
events.sort()
block = set()
ans = [-1] * Q
for e in events:
    if e[1] == 0:
        block.remove(e[2])
    elif e[1] == 1:
        block.add(e[2])
    else:
        if block:
            ans[e[2]] = min(block)
print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import collections, sys
input = sys.stdin.readline
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
events = []
for stx in STX:
    s, t, x = stx
    events += [[s - x, 1, x], [t - x, 0, x]]
for d in D:
    events += [[d, 2]]
events.sort()
block = set()
ans = []
for e in events:
    if e[1] == 0:
        block.remove(e[2])
    elif e[1] == 1:
        block.add(e[2])
    else:
        if block:
            ans += [min(block)]
        else:
            ans += [-1]
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import collections, sys
input = sys.stdin.readline
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
events = []
for stx in STX:
    s, t, x = stx
    events += [[s - x, 1, x], [t - x, 0, x]]
for d in D:
    events += [[d, 2]]
events.sort()
block = set()
for e in events:
    if e[1] == 0:
        block.remove(e[2])
    elif e[1] == 1:
        block.add(e[2])
    else:
        if block:
            print(min(block))
        else:
            print(-1)

Submission status: Time Limit Exceeded

Solution code:
import collections, sys
from heapq import *
input = sys.stdin.readline
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
event = []
for stx in STX:
    s, t, x = stx
    heappush(event, [s - x, 1, x])
    heappush(event, [t - x, 0, x])
for d in D:
    heappush(event, [d, 2])
block = set()
while event:
    e = heappop(event)
    if e[1] == 0:
        block.remove(e[2])
    elif e[1] == 1:
        block.add(e[2])
    else:
        if block:
            print(min(block))
        else:
            print(-1)

Submission status: Time Limit Exceeded

Solution code:
import collections, sys
from heapq import *
input = sys.stdin.readline
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
event = []
for stx in STX:
    s, t, x = stx
    heappush(event, [s - x, 1, x])
    heappush(event, [t - x, 0, x])
for d in D:
    heappush(event, [d, 2])
event.sort()
block = set()
for e in event:
    if e[1] == 0:
        block.remove(e[2])
    elif e[1] == 1:
        block.add(e[2])
    else:
        if block:
            print(min(block))
        else:
            print(-1)

Submission status: Time Limit Exceeded

Solution code:
### 解説見てから書いたコード
import sys
input = sys.stdin.readline

n, q = map(int, input().split())
events = [None] * 2*n
stop_points = []
for i in range(n):
    si, ti, xi = map(int, input().split())
    events[2*i] = ([si-xi,  1, xi])
    events[2*i+1] = ([ti-xi, -1, xi])
d = [int(input()) for i in range(q)]
events.sort()

event_i = 0
events_len = len(events)
for di in d:
    while event_i < events_len and events[event_i][0] <= di:
        if events[event_i][1] == 1:
            stop_points.append(events[event_i][2])
        else:
            stop_points.remove(events[event_i][2])
        event_i += 1
    d_stop = -1 if stop_points == [] else min(stop_points)
    print(d_stop)

Submission status: Time Limit Exceeded

Solution code:
### 解説見てから書いたコード
import sys
input = sys.stdin.readline

n, q = map(int, input().split())
events = [None] * 2*n
stop_points = []
append = stop_points.append
remove = stop_points.remove

for i in range(n):
    si, ti, xi = map(int, input().split())
    events[2*i] = ([si-xi,  1, xi])
    events[2*i+1] = ([ti-xi, -1, xi])
d = [int(input()) for i in range(q)]
events.sort()

event_i = 0
events_len = len(events)
for di in d:
    while event_i < events_len and events[event_i][0] <= di:
        if events[event_i][1] == 1:
            append(events[event_i][2])
        else:
            remove(events[event_i][2])
        event_i += 1
    d_stop = -1 if stop_points == [] else min(stop_points)
    print(d_stop)

Submission status: Time Limit Exceeded

Solution code:
### 解説見てから書いたコード
import sys
import numpy as np
input = sys.stdin.readline

n, q = map(int, input().split())
events = [None] * 2*n
stop_points = []
append = stop_points.append
remove = stop_points.remove

for i in range(n):
    si, ti, xi = map(int, input().split())
    events[2*i] = ([si-xi,  1, xi])
    events[2*i+1] = ([ti-xi, -1, xi])
d = [int(input()) for i in range(q)]
events.sort()

event_i = 0
events_len = len(events)
for di in d:
    while event_i < events_len and events[event_i][0] <= di:
        if events[event_i][1] == 1:
            append(events[event_i][2])
        else:
            remove(events[event_i][2])
        event_i += 1
    d_stop = -1 if stop_points == [] else np.min(stop_points)
    print(d_stop)

Submission status: Time Limit Exceeded

Solution code:
### 解説見てから書いたコード
import sys
input = sys.stdin.readline

n, q = map(int, input().split())
events = [None] * 2*n
stop_points = []
for i in range(n):
    si, ti, xi = map(int, input().split())
    events[2*i] = ([si-xi,  1, xi])
    events[2*i+1] = ([ti-xi, -1, xi])
d = [int(input()) for i in range(q)]
events.sort()

event_i = 0
events_len = len(events)
for di in d:
    while event_i < events_len and events[event_i][0] <= di:
        if events[event_i][1] == 1:
            stop_points.append(events[event_i][2])
        else:
            stop_points.remove(events[event_i][2])
        event_i += 1
    d_stop = -1 if len(stop_points) == 0 else min(stop_points)
    print(d_stop)

Submission status: Time Limit Exceeded

Solution code:
### 解説見てから書いたコード
n, q = map(int, input().split())
events = []
stop_points = []
for i in range(n):
    si, ti, xi = map(int, input().split())
    events.append([si-xi,  True, xi])
    events.append([ti-xi, False, xi])
d = [int(input()) for i in range(q)]
events.sort()

event_i = 0
events_len = len(events)
for di in d:
    while event_i < events_len and events[event_i][0] <= di:
        if events[event_i][1]:
            stop_points.append(events[event_i][2])
        else:
            stop_points.remove(events[event_i][2])
        event_i += 1
    d_stop = -1 if len(stop_points) == 0 else min(stop_points)
    print(d_stop)