Roadwork - abc 128 e
解法 1 (set)
ある工事に対して, そこでストップになる人を求める
] の間 X が工事中ということは,
] に X にくる人がストップ
すなわち, ] にスタートする人がストップ
すべての工事に対して, ] にスタートする人をストップさせていく
すべての工事に対して, D を重複して見ないようにする
時間計算量的に
set を使う
工事を X で sort する
X が小さいのでストップさせたら, X が大きいのでストップすることはない
ソースコード
https://atcoder.jp/contests/abc128/submissions/11662783
解法 2 (遅延セグ木)
上の解法で, 重複を考えなくてもいい方法
区間の値を X にするのが O(logQ) でできたらいい
遅延セグ木ならできる
X を大きい順で見たら, 最終的に適応されるのは X が一番小さいのになる
ソースコード
https://atcoder.jp/contests/abc128/submissions/11657782
