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: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    """
    とりあえず，S,TはXだけ左にずらして，0秒の時にどの時間ならXで止まるかにする．
    そのあと，グラフ(x-tグラフ)を書いて，縦棒を左から動かしていく（イベントソート）
    通行止めとなるXを複数持っておく必要があり，追加，参照，削除の機能が欲しい
    """

    ##############################
    from bisect import bisect_left, bisect_right, insort_right
    class SquareSkipList:
        # SkipList の層数を 2 にした感じの何か
        # std::multiset の代用になる

        def __init__(self, values=None, sorted_=False, square=1000, seed=42):
            # values: 初期値のリスト
            # sorted_: 初期値がソート済みであるか
            # square: 最大データ数の平方根
            # seed: 乱数のシード
            ### pop関数は　for を回すので重め、使うなら square パラメータを大きめにするべき

            self.cnt=0#要素数を持っておくか
            inf = float("inf")
            self.square = square
            if values is None:
                self.rand_y = seed
                self.layer1 = [inf]
                self.layer0 = [[]]
            else:
                self.layer1 = layer1 = []
                self.layer0 = layer0 = []
                if not sorted_:
                    values.sort()
                y = seed
                l0 = []
                for v in values:
                    y ^= (y & 0x7ffff) << 13
                    y ^= y >> 17
                    y ^= (y & 0x7ffffff) << 5
                    if y % square == 0:
                        layer0.append(l0)
                        l0 = []
                        layer1.append(v)
                    else:
                        l0.append(v)
                layer1.append(inf)
                layer0.append(l0)
                self.rand_y = y

        def add(self, x):  # 要素の追加  # O(sqrt(n))
            # xorshift
            y = self.rand_y
            y ^= (y & 0x7ffff) << 13
            y ^= y >> 17
            y ^= (y & 0x7ffffff) << 5
            self.rand_y = y

            if y % self.square == 0:
                layer1, layer0 = self.layer1, self.layer0
                idx1 = bisect_right(layer1, x)
                layer1.insert(idx1, x)
                layer0_idx1 = layer0[idx1]
                idx0 = bisect_right(layer0_idx1, x)
                layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない  # dict 微妙だった
                del layer0_idx1[idx0:]
            else:
                idx1 = bisect_right(self.layer1, x)
                insort_right(self.layer0[idx1], x)

            self.cnt+=1#追加

        def remove(self, x):  # 要素の削除  # O(sqrt(n))
            # x が存在しない場合、x 以上の最小の要素が削除される
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                del self.layer1[idx1]
                self.layer0[idx1] += self.layer0.pop(idx1+1)
            else:
                del layer0_idx1[idx0]

            self.cnt-=1

        def search_higher_equal(self, x):  # x 以上の最小の値を返す  O(log(n))
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
            idx1 = bisect_right(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return self.layer1[idx1]
            return layer0_idx1[idx0]

        def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
            #x未満のものがない場合，infが返るかも！！！  
            idx1 = bisect_left(self.layer1, x)
            layer0_idx1 = self.layer0[idx1]
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  # layer0_idx1 が空の場合とすべて x 以上の場合
                return self.layer1[idx1-1]
            return layer0_idx1[idx0-1]

        def pop(self, idx):
            # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
            # O(sqrt(n))
            # for を回すので重め、使うなら square パラメータを大きめにするべき
            self.cnt-=1
            layer0 = self.layer0
            s = -1
            for i, l0 in enumerate(layer0):
                s += len(l0) + 1
                if s >= idx:
                    break
            if s==idx:
                layer0[i] += layer0.pop(i+1)
                return self.layer1.pop(i)
            else:
                return layer0[i].pop(idx-s)


        def all(self):
            print(self.layer1)
            print(self.layer0)

        def len(self):
            return self.cnt

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


    N,Q=MI()
    L=[]#0なら追加，1なら削除，2ならクエリ，半開区間なので順番大事
    for _ in range(N):
        s,t,x=MI()
        s-=x
        t-=x
        L.append([s,0,x])
        L.append([t,1,x])
        
    #制約よりDは昇順
    for _ in range(Q):
        d=I()
        L.append([d,2,0])#3つに揃えておくか
        
    L.sort()
    anss=[]
    inf=10**10
    ssl = SquareSkipList(square=2000)
    ssl.add(inf)
    
    for t,q,x in L:
        if q==0:
            ssl.add(x)
        elif q==2:
            temp=ssl.search_higher_equal(-1)#最小値検索
            if temp==inf:
                ans=-1
            else:
                ans=temp
            anss.append(ans)
        else:
            ssl.remove(x)
            
    for i in range(Q):
        print(anss[i])
                
            
        
        
    
    
main()

Submission status: Accepted

Solution code:
import heapq

class BalancingTree:
    def __init__(self):
        self.p = []
        self.q = []

    def insert(self, x):
        heapq.heappush(self.p, x)

    def erase(self, x):
        heapq.heappush(self.q, x)

    def minimum(self):
        while self.q and self.p[0] == self.q[0]:
            heapq.heappop(self.p)
            heapq.heappop(self.q)
        return self.p[0] if self.p else -1


n, q = map(int, input().split())
events = []
for _ in range(n):
    s, t, x = map(int, input().split())
    events.append((s-x, 1, x))
    events.append((t-x, 0, x))
for _ in range(q):
    d = int(input())
    events.append((d, 2, 0))

events.sort()
bt = BalancingTree()
for _, i, k in events:
    if i == 1:
        bt.insert(k)
    elif i == 0:
        bt.erase(k)
    else:
        print(bt.minimum())

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# 各queryについてO(n)で答える
# 問題を言い換えると　　

# 地点Xに到着するのは時間 Di + Xの時
# S <= Di + X < Tとなる[S, T, N]がなければ通過できる
# SについてXの早い順にソートする

# 各Dについて、どのSまで通過できるかを各O(1)で答える？

N,Q = getNM()
# taskに
# 0:通行止め時間帯のスタート
# 1:通行止め時間帯のゴール
# 2:人
# を入れ、全部まとめて処理する
task = []

STX = [getList() for _ in range(N)]
for s, t, x in STX:
    task.append((t - x, 0, x)) # xで止まらなくなる
    task.append((s - x, 1, x)) # xで止まる

for i in range(Q):
    d = getN()
    task.append((d, 2, i)) # 止まる位置を答える
answer = [-1] * Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapで最小値を先頭に保つ
heapq.heapify(se_hp)

# 小さい時刻から順に見ていく
# 人ciについてどの範囲cjの範囲内に入っているか
for a, b, c in task:
    # ゴール位置についての情報なら
    if b == 0:
        # そのゴールに対応するスタート位置を取り除く
        se.remove(c)
    # スタートについての情報なら
    elif b == 1:
        # スタート位置を追加する
        se.add(c)
        # スタート位置の最小値候補に入れる
        heapq.heappush(se_hp, c)
    # 人についての情報なら
    else:
        # se_hpの最小値がseにない（用済みのものが残っている）間
        # またはse_hpを抜き切るまで
        while se_hp and se_hp[0] not in se:
            heapq.heappop(se_hp)
        if se_hp:
            answer[c] = se_hp[0]
        else:
            answer[c] = -1
    # (-3, 1, 10) 10のものについてスタートを追加
    # se:{10} se_hp:[10]
    # (-1, 1, 2) 2のものについてスタートを追加
    # se:{10, 2} se_hp:[2, 10]
    # (0, 2, 0) 人0について調べる
    # se:{10, 2} se_hp[2, 10]
    # (1, 0, 2) 2のものについてゴールが来たのでスタート位置を取り除く
    # se:{10} se_hp:[2, 10] se_hpに余計なものが残る
    # (1, 1, 2) 2のものについてスタート位置をまた追加
    # se:{10, 2} se_hp:[2, 10, 2]

for i in answer:
    print(i)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# 各queryについてO(n)で答える
# 問題を言い換えると　　

# 地点Xに到着するのは時間 Di + Xの時
# S <= Di + X < Tとなる[S, T, N]がなければ通過できる
# SについてXの早い順にソートする

# 各Dについて、どのSまで通過できるかを各O(1)で答える？

N,Q = getNM()
# taskに
# 0:通行止め時間帯のスタート
# 1:通行止め時間帯のゴール
# 2:人
# を入れ、全部まとめて処理する
task = []

STX = [getList() for _ in range(N)]
for s, t, x in STX:
    task.append((t - x, 0, x)) # xで止まらなくなる
    task.append((s - x, 1, x)) # xで止まる

for i in range(Q):
    d = getN()
    task.append((d, 2, i)) # 止まる位置を答える
answer = [-1] * Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapで最小値を先頭に保つ
heapq.heapify(se_hp)

# 小さい時刻から順に見ていく
for a, b, c in task:
    # ゴール位置についての情報なら
    if b == 0:
        # とり除く
        se.remove(c)
    # スタートについての情報なら
    elif b == 1:
        se.add(c)
        heapq.heappush(se_hp, c)
    # 人についての情報なら
    else:
        # se_hpを抜き切るか、se_hpの最小値がseにある場合はエンド
        while se_hp and se_hp[0] not in se:
            heapq.heappop(se_hp)
        if se_hp:
            answer[c] = se_hp[0]
        else:
            answer[c] = -1

for i in answer:
    print(i)

Submission status: Accepted

Solution code:
import sys
import bisect
from heapq import heappop, heappush, heapify
input = sys.stdin.readline
from itertools import chain
sys.setrecursionlimit(10**9)
N,Q= map(int,input().split())
STX = [list(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

inf = 10**15
TEMP = [[(s-x,True,x),(t-x,False,x)] for s,t,x in STX] + [[(-inf,True,inf),(inf,False,inf)]]
PFX = sorted(list(chain(*TEMP)))

addq = [inf]
delq = [inf+1]
D.append(inf)
iterD = iter(D)

d = next(iterD)
for p,f,x in PFX:
    while d < p:
        ans = addq[0] if not addq[0] == inf else -1
        print(ans)
        d = next(iterD)
        if d == inf:
            exit()
    if f:
        heappush(addq, x)
    else:
        heappush(delq, x)
    while addq[0] == delq[0]:
        heappop(addq)
        heappop(delq)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
            self.depth=n.bit_length()
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s
        
        def lower_bound(self,x):
            sum_=0
            pos=0
            for i in range(self.depth,-1,-1):
                k=pos+(1<<i)
                if k<=self.num and sum_+self.dat[k]<x:
                    sum_+=self.dat[k]
                    pos+=1<<i
            return pos, sum_
    
    N,Q=map(int,input().split())
    S,T,X=[0]*N,[0]*N,[0]*N
    for i in range(N):
        S[i],T[i],X[i]=map(int,input().split())
    unique_X=sorted(list(set(X)))
    d={unique_X[i]:i for i,x in enumerate(unique_X)}
    l=[0]*(N*2+Q)
    for i in range(N):
        l[i*2]=((S[i]-X[i])<<40)+(1<<20)+d[X[i]]
        l[i*2+1]=((T[i]-X[i])<<40)+d[X[i]]
    for i in range(N*2,N*2+Q):
        l[i]=(int(input())<<40)+(2<<20)
    l.sort()
    mask=(1<<20)-1
    b=BIT(len(unique_X))
    for tqx in l:
        x=tqx&mask
        q=(tqx>>20)&mask
        t=(tqx>>40)&mask
        if q==0:
            b.add(x,-1)
        elif q==1:
            b.add(x,1)
        else:
            res,_=b.lower_bound(1)
            print(unique_X[res] if res<len(unique_X) else -1)
        


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import bisect
from heapq import heappop, heappush, heapify
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
N,Q= map(int,input().split())
STX = [list(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

'''
import random
N = 2*10**5
Q = 2*10**5
STX = []
for i in range(N):
    S,T = sorted([random.randint(0,10**9-1) for i in range(2)])
    if S == T:
        T += 1
    X = random.randint(1,10**9)
    STX.append([S,T,X])
D = sorted([random.randint(0,10*9) for i in range(Q)])
'''

inf = 10**15
PFXS = [(s-x,True,x) for s,t,x in STX]
PFXT = [(t-x,False,x) for s,t,x in STX]
PFX = PFXS + PFXT
PFX.append((-inf,True,inf))
PFX.append((inf,False,inf))
PFX.sort()

addq = [inf]
delq = [inf+1]
iterD = iter(D)

d = next(iterD)
for p,f,x in PFX:
    while d < p:
        ans = addq[0] if not addq[0] == inf else -1
        print(ans)
        try:
            d = next(iterD)
        except:
            exit()
    if f:
        heappush(addq, x)
    else:
        heappush(delq, x)
    while addq[0] == delq[0]:
        heappop(addq)
        heappop(delq)

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
stx=[list(map(int,input().split())) for _ in range(n)]
d=[int(input()) for _ in range(q)]
inf=float('inf')

import heapq
class pqheap:
  def __init__(self,key=None):
    self.p = list()
    self.q = list()

  def insert(self,x):
    heapq.heappush(self.p, x)
    return

  def erase(self,x):
    heapq.heappush(self.q, x)
    return

  def minimum(self):
    while self.q and self.p[0] == self.q[0]:
      heapq.heappop(self.p)
      heapq.heappop(self.q)
    return self.p[0] if len(self.p)>0 else -1
memopush={}
memopop={}
from bisect import bisect_left,bisect_right
for s,t,x in stx:
  l,r=max(0,s-x),max(0,t-x)
  # 出発時刻が[l,r)の人の進む距離がxで抑えられる
  if l in memopush:
    memopush[l].append(x)
  else:
    memopush[l]=[x]
  if r in memopop:
    memopop[r].append(x)
  else:
    memopop[r]=[x]
keys=list(set(memopush.keys()).union(set(memopop.keys())))
keys.sort()
pq=pqheap()
dct=[[-1,-1]]
for k in keys:
  if k in memopush:
    for v in memopush[k]:
      pq.insert(v)
  if k in memopop:
    for v in memopop[k]:
      pq.erase(v)
  dct.append([k,pq.minimum()])
i=0
for x in d:
  while i+1<len(dct) and dct[i+1][0]<=x:
    i+=1
  if i>=len(dct):
    print(-1)
  else:
    print(dct[i][1])

#print(dct)

Submission status: Accepted

Solution code:
from heapq import heapify, heappush, heappop 

INF = 1001001001

N, Q = map(int, input().split())
STXs = [tuple(map(int, input().split())) for _ in range(N)]
Ds = [int(input()) for _ in range(Q)]

#S-X, T-X, X
future_block = [(S - X, T - X, X) for S, T, X in STXs]
future_block.append((INF, INF, INF)) #sentinel
heapify(future_block)

#T-X, X
current_block = [(INF, INF)] #sentinel
current_min_pair = (INF, INF)

for D in Ds:
    while future_block[0][0] <= D:
        s_x, t_x, x = heappop(future_block)
        if current_min_pair[1] > x:
            current_min_pair = (t_x, x)
        heappush(current_block, (t_x, x))
    
    search_min_flg = False
    while current_block[0][0] <= D:
        if current_min_pair == heappop(current_block):
            search_min_flg = True
    if search_min_flg:
        current_min_pair = min(current_block, key = lambda t: t[1])

    print(-1 if current_min_pair[1] == INF else current_min_pair[1])

Submission status: Accepted

Solution code:
import heapq

N, Q = map(int,input().split())

events = []

for _ in range(N):
    S, T, X = map(int,input().split())

    events.append([S-X, 1, X])
    events.append([T-X, 0, X])

for _ in range(Q):
    D = int(input())
    events.append([D,2,0])

events.sort()

closed = set()
que = []

idx = 0
for time, flag, position in events:
    if flag == 0:
        closed.remove(position)
    elif flag == 1:
        heapq.heappush(que, position)
        closed.add(position)
    else:
        while len(que) > 0 and que[0] not in closed:
            heapq.heappop(que)

        if len(que) > 0:
            print(que[0])
        else:
            print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, q = map(int,input().split())
S = [list(map(int,input().split())) for i in range(n)]
D = [int(input()) for i in range(q)]

A = []
for i in range(n):
    s = S[i][0]
    t = S[i][1]
    x = S[i][2]
    A.append([s-x-0.5, x, i, 0])
    A.append([t-x-0.5, x, i, 1])
for i in range(q):
    A.append([D[i], 0, 0, 2])

A.sort()
from heapq import heappop, heappush
Q = []
F = [0] * n
for i in range(len(A)):
    s = A[i][0]
    x = A[i][1]
    j = A[i][2]
    f = A[i][3]
    if f == 0:
        heappush(Q, [x, j])
        F[j] = 1
    elif f == 1:
        F[j] = 0
    elif f == 2:
        while len(Q) > 0 and F[Q[0][1]] == 0:
            heappop(Q)
        if len(Q) > 0:
            print(Q[0][0])
        else:
            print(-1)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


n, q = map(int, input().split())
events = []

for i in range(n):
    s, t, x = map(int, input().split())
    if t >= x:
        events.append([t - x, 0, x])
        events.append([s - x, 1, x])
for i in range(q):
    d = int(input())
    events.append([d, 2, i])
events.sort()

dist = [-1] * q
walker = []
working = set()
heap = []
for t, kind, x in events:
    if kind == 0:
        working.remove(x)
    elif kind == 1:
        working.add(x)
        heappush(heap, x)
    elif working:
        while not heap[0] in working:
            heappop(heap)
        dist[x] = heap[0]

print(*dist, sep="\n")

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


n, q = map(int, input().split())
events = []

for i in range(n):
    s, t, x = map(int, input().split())
    if t >= x:
        events.append([t - x, 0, x])
        events.append([s - x, 1, x])
for i in range(q):
    d = int(input())
    events.append([d, 2, i])
events.sort()

dist = [-1] * q
walker = []
working = set()
heap = []
for t, kind, x in events:
    if kind == 0:
        working.remove(x)
    elif kind == 1:
        working.add(x)
        heappush(heap, x)
    elif working:
        while not heap[0] in working:
            heappop(heap)
        dist[x] = heap[0]

for d in dist:
    print(d)

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

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

# Binary Indexed Tree
# Bit.add(i,x)    : add x at i-th value
# Bit.sum(i)      : get sum up to i-th value



show_flg=False
#show_flg=True

ans=0

a=[]
n,q=LI()
for i in range(n):
    s,t,x=LI()
    a+=(x,(s-x,t-x)),
a.sort(key=lambda x:-x[1][0])

d=NI(q)

p=[]
g=[]
for i in range(q):
    c=d[i]
    while a and a[-1][1][0]<=c:
        x,(l,r)=a.pop()
        heappush(p,(x,(l,r)))
    
    while p and p[0][1][1]<=c:
        x,(l,r)=heappop(p)

    if p:
        ans=p[0][0]
    else:
        ans=-1
    g+=ans,

for i in g:
    print(i)

Submission status: Accepted

Solution code:
from heapq import heappop,heappush

N,Q=map(int,input().split())


event=[]
q=[]
for _ in range(N):
    S,T,X=map(int,input().split())
    event.append([S-X,1,X])
    event.append([T-X,-1,X])

for i in range(Q):
    event.append([int(input()),2,i])

stop_set=set()
event.sort()
q=[]

for pos,m,x in event:
    if m==-1:
        stop_set.remove(x)
        
    elif m==1:
        #heappushする時点でqはソートされている
        heappush(q,x)
        stop_set.add(x)
    
    else:
        #この時点でのstop_setは、i番目の人が遭遇する通行止めの座標
        #この時点でのqは今までstopになった座標
        while q:
            #qはソート済なので、q[0]は最小値　それがstop_setから外れている場合、heappopでそれを排除する
            if q[0] not in stop_set:
                heappop(q)
            #q[0]がstop_setから外れてない場合、それ以降のqも外れていないのでbreak    
            else:
                break

        if q:
            print(q[0])
        else:
            print(-1)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from operator import itemgetter
import sys
input = sys.stdin.readline


class PseudoSet():
    def __init__(self):
        self.s = []  # set
        self.e = []  # erase candidate

    def insert(self, x):
        heappush(self.s, x)

    def erase(self, x):
        heappush(self.e, x)

    def get_min(self):
        while self.e and self.e[0] == self.s[0]:
            _ = heappop(self.s)
            _ = heappop(self.e)
        return self.s[0] if len(self.s) > 0 else None


n, q = map(int, input().split())
events = []
for i in range(n):
    s, t, x = map(int, input().split())
    events.append((s - x, +1, x))
    events.append((t - x, -1, x))
for i in range(q):
    d = int(input())
    events.append((d, 2, i))

ans = [-1] * q
events.sort(key=itemgetter(0, 1))
# print(events)
ps = PseudoSet()
for c, t, z in events:
    if t == 1:
        ps.insert(z)
    elif t == -1:
        ps.erase(z)
    else:
        # t == 2
        m = ps.get_min()
        if m is not None:
            ans[z] = m

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from operator import itemgetter
import sys
input = sys.stdin.readline


class PseudoSet():
    def __init__(self):
        self.s = []  # set
        self.e = []  # erase candidate

    def insert(self, x):
        heappush(self.s, x)

    def erase(self, x):
        heappush(self.e, x)

    def get_min(self):
        while self.e and self.e[0] == self.s[0]:
            _ = heappop(self.s)
            _ = heappop(self.e)
        return self.s[0] if len(self.s) > 0 else None


n, q = map(int, input().split())
stx = []
events = []
for i in range(n):
    s, t, x = map(int, input().split())
    stx.append((s, t, x))
    events.append((s - x, +1, i))
    events.append((t - x, -1, i))
for i in range(q):
    d = int(input())
    events.append((d, 2, i))

ans = [-1] * q
events.sort(key=itemgetter(0, 1))
# print(events)
ps = PseudoSet()
for c, t, i in events:
    if t == 1:
        ps.insert(stx[i][2])
    elif t == -1:
        ps.erase(stx[i][2])
    else:
        # t == 0
        m = ps.get_min()
        if m is not None:
            ans[i] = m

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

Submission status: Accepted

Solution code:
# roadwork
import heapq
N, Q = map(int, input().split())
que = []
ans = [-1 for i in range(Q)]
D = [0 for i in range(N)]
heap = []
heapq.heapify(heap)
Set = set([])
for i in range(N):
    s, t, x = map(int, input().split())
    que.append((s-x, 0, i))  # append
    que.append((t-x, 1, i))  # remove
    D[i] = x

for i in range(Q):
    d = int(input())
    que.append((d, 2, i))  # querie

que.sort(key=lambda x: x[0])

for x in que:
    demand = x[1]
    if demand == 0:
        # append
        heapq.heappush(heap, (D[x[2]], x[2]))
        Set.add(x[2])
    elif demand == 1:
        # remove
        Set.remove(x[2])
    else:
        # querie
        flag = True
        while heap and flag:
            distance, index = heapq.heappop(heap)
            if index in Set:
                ans[x[2]] = distance
                heapq.heappush(heap, (distance, index))
                flag = False
for i in range(Q):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
import bisect

N,Q = map(int,input().split())
# STX = [list(map(int,input().split())) for _ in range (N)]
STX = []
vals = set()
for _ in range(N):
    s,t,x = map(int,input().split())
    STX.append((max(0,s-x), max(0,t-x), x))
    vals.add(max(0,s-x))
    vals.add(max(0,t-x))
D = [int(input()) for _ in range(Q)]
for d in D:
    vals.add(d)
vals = list(vals)
vals.sort()
L = len(vals)
mapping = [-1]*(L+1)
imos = [[] for _ in range(L+1)]
STX.sort(key=lambda x:x[2])
priority = 0 
for s,t,x in STX:
    s1 = bisect.bisect_left(vals, s)
    t1 = bisect.bisect_left(vals, t)
    imos[s1].append([1, priority, x])
    imos[t1].append([0, priority, x])
    priority += 1

import heapq
cur = -1
cur_priority = 10**9
que = [(cur_priority, cur)]
valid_priority = [True]*(N+1)
for i in range(L+1):
    for f,p,x in  imos[i]:
        if f:
            heapq.heappush(que, (p, x))
        else:
            valid_priority[p] = False
    
    while que[0][1]!=-1 and valid_priority[que[0][0]]==False:
        heapq.heappop(que)
    mapping[i] = que[0][1]

for d in D:
    d1 = bisect.bisect_left(vals, d)
    print(mapping[d1])