ABC128 E - Roadwork - あっとのTECH LOG

問題原文

問題要旨

数直線と見なすことのできる道路がある。
この道路で $N$ 回工事が行われる。工事 $i$ は、時刻 [S_i - 0.5] から時刻 [T_i - 0.5] まで座標 $X_i$ を通行不能にする。
また $Q$ 人の人がいる。人 $j$ は時刻 $D_j$ に座標0から数直線を出発し、時速1で右に進む。工事中の座標にたどり着いたら、そこで止まる。各人について、進む距離を求めよ。ただし、無限に進み続けられる場合は -1とせよ。

$1 \leq N \leq 2×10^{5}$
$0 \leq S_i ＜ T_i \leq 10^{9}$
$1 \leq X_i \leq 10^{9}$
$0 \leq D_i \leq D_j \leq 10^{9}(i ＜ j)$
$i \neq j$ のとき、 $[S_i, Ti)$ と $[S_j, T_j)$ は重ならない

解法

まず、ある工事 $i$ に引っかかるような人は、時刻 $[S_i - x, S_j - x)$ に出発した人と言い換えて良い。
また今回のような、有効期限付き条件 を取り扱うのには、イベントソートが有効。

イメージは、「今通行止めの座標を管理するもの」に「座標追加イベント」と「座標削除イベント」で操作をしていく。あるタイミングからスイッチを入れておいて、あるタイミングでスイッチを切るイメージ。「イベントをどこまで見たか？」を管理するマーカーもあるとよい。
各人の判定においては、今通行止めされている座標のうち最小のもの（なければ−１）とすればよい。

実装

あまりにも罠が多く、高速化があまりにも地獄。
まず、 今通行止めの座標の中から最小値を取り出すのに、min(set)を使うことはできない。
min(set) は実は O(N) で間に合わない。。。

また、各人のチェックについてもイベント化する方が早くなる。
またイベントの持ち方はタプルを使う。

if _name_ == '__main__' も使う。
sys.stdin.readline() も忘れずに使う。

最小値の計算には heapq を使う。
現在の最小値候補が、現在通行止めの座標の中に入っているまで、heapq から取り出し続ける。

イベントの優先順位にも注意する。
優先度は、削除 → 追加 → 判定の順。
判定が最後なのはそれはそうとして、削除が追加より先なのが不思議に思えるが、ある１つの工事については削除イベントが追加イベントより先に来ることはないので大丈夫。むしろ追加→削除だとある２つの工事で同じ座標を追加、追加、削除、削除、とするときに、途中で set がこわれる。

defalultdict を使えば回避できるが、使わない方が早いはず。

あと PyPyじゃなくてPythonでないと通らない。setとかheapqが遅いんだろうか。。。わからない

def main():

    import sys
    import heapq

    N, Q = map(int, sys.stdin.readline().split())
    events = []

    for i in range(N):
        s, t, x = map(int, sys.stdin.readline().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, 0))  # チェックイベント

    events.sort()
    events.append([float('inf'), 'guard', None])

    i = 0
    closing = set()
    hq = []  # 最小値を高速に入手するため
    while d >= events[i][0]:
        time, event, x = events[i]
        if event == 1:
            closing.add(x)
            heapq.heappush(hq, x)

        elif event == -1:
            closing.remove(x)

        else:
            while hq and (hq[0] not in closing):
                heapq.heappop(hq)

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

        i += 1


if __name__ == '__main__':
    main()

感想

解法の核は、

at274.hatenablog.com

と似ている。

でも実装が地獄。ほんとに地獄。
Pythonの min(set) は O(N) だということを、心に刻んでおく。。。
あと細かい高速化テクニックも。