ABC128 E. Roadwork
問題
東西に無限に続く1本の大通りがあり、数直線とみなせる。
大通りでN回の工事が行われ、i番目の道路工事はSi-0.5からTi-0.5の時刻にXi地点を通行止めにする。
Q人の人が座標0におり、i番目の人は時刻Diで出発し、速度1で進む。
しかし、工事中の通行止めの地点に到達するとそこで止まる。
各人の進む距離を求めよ。無限に進む場合は-1を返せ。
制約
- 1 <= N, Q <= 2*10^5
- 0 <= Si < Ti <= 10^9
- 1 <= Xi <= 10^9
- 0 <= D1 < ... < DQ <= 10^9
- 同じ地点で複数の工事が時刻が重なるように実施はされない
解法1
各工事について、いつ出発すればその工事地点で止まることになるかを考える。
これは簡単で、[Si-Xi, Ti-Xi)の時間に出発する人がこの工事地点で止まりうる。
ただし、複数の工事がある場合は、一番Xiが小さいところで止まる。
範囲更新できればよいので、座標圧縮したものに対して遅延セグメント木でXiが大きい方から入れていき、小さい時刻から人の出発時刻とセグメント木の値を見比べて答えていけばよい。
(座圧の時に、各人の時刻も一緒にいれておくと、簡単に問い合わせできる)
解法2
遅延セグメント木ではなく、setを使って求めることができる。
setに各人の時刻を入れておき、工事のXiが小さい方から、[Si-Xi, Ti-Xi)の範囲にある人を取り除いていけばよい。
Si-Xiをlower_boundで探して、イテレータを回してTi-Xi未満の人をeraseしていく。
