ABC128 E - Roadwork (500)
出てくる座標はすべて座標圧縮する
通行止め地点と時間からどのタイミングで出発した時にそこで通行止めになるか分かる
通行止め情報をXの昇順にソート
座標圧縮した各時間に各通行止めの開始地点と終了地点を追加する
各時間をなめて、追加した情報からその時間がどこで通行止めになるかを入れる
setで現在含まれる通行止めを持って、一番手前にあるものを使う
各時間に対してどこで通行止めになるのかが求められたので、各
$ D_i
に対応する地点を出力すればOK
問題:
https://atcoder.jp/contests/abc128/tasks/abc128_e
提出:
https://atcoder.jp/contests/abc128/submissions/5652919
#AtCoder
#ABC
#ABC128
#E
#500pt
#O(NlogN)