AtCoder Beginner Contest 128 E Roadwork - kamojirobrothersのブログ

AtCoder Beginner Contest 128はリアルタイムで参加できなかった。
そのE問題が面白かったので、解説する。
問題はこれ
E - Roadwork。

解説

一言で言うと、時刻 $0$ で考えれば十分。
簡単な場合に、説明する。
Aさんが、時刻 $d$ に出発して、時刻 $s$ から $t$ に道路工事が行われているとする。
Aさんが時刻 $x$ で座標 $y$ にいるとすると、
$y = x -d$ となる。
平行移動みたいなことをすると、
Aさんが、通行止めに合うことと、 $-t+1 <= -d <= -s+1$ は等しい。

問題の設定でこれを書き直すと、通行止めに合うのは、
$X_i-T_i+1 <= -D_j <= X_i-S_i$ のときになる。

各 $j$ に対して、
$\min\{X_i | X_i-T_i+1 <= -D_j <= X_i-S_i \ ( 1 \leq i \leq N)\} =: \min M_j$
を求めれば良い。
見ている集合が空なら、通行止めに当たらない。

こうすると、
$\{-D_i\}_{i=1}^{Q}$ と $\{(X_i-T_i+1, X_i-S_i)\}_{i=1}^N$ をソートしてどうにかすれば良い気がしてくる。

そして、優先度付きキューを使って、 $-D_j$ と重なる通行止めたち $M_j$ の最小値を管理するとうまくいく。

解答

import heapq
from collections import deque
N, Q = map( int, input().split())
H = [(0,0,0) for _ in range(N)]
for i in range(N):
    s, t, x = map( int, input().split())
    H[i] = (x-t+1, x-s, x)
D = [ ( -int( input()), i) for i in range(Q)]
D.sort()
H.sort()
d = deque(H)
q = []
ANS = [0]*Q
for i in range(Q):
    t, j = D[i]
    while d:
        if d[0][0] <= t:
            _, s, x = d.popleft()
            heapq.heappush(q,(x,s))
        else:
            break
    while q:
        if q[0][1] >= t:
            break
        heapq.heappop(q)
    if not q:
        ANS[j] = -1
    else:
        ANS[j] = q[0][0]
for ans in ANS:
    print( ans)