ABC128 E - Roadwork - ツバサの備忘録

解法

0.5うんぬんという条件がありますが、結局は時刻 $[S_{i},T_{i} )$ の間で座標 $X_{i}$ に到着した場合、その人はそれ以上進めない、ということになります。
これを言い換えると、時刻 $[S_{i}-X_{i},T_{i}-X_{i})$ の間に座標 $0$ を出発する人は、少なくとも $X_{i}$ より先に進むことができなくなります。
$D_{i}$ に出発する人について、この $X_{i}$ の最小値(そもそも存在しなければ答えは $-1$ です)を求めれば答えとなります。
ここで、通れなくなる時刻を区間としてではなく、それぞれ開始と終了の2つに分けてあげると、ある $D_{i}$ については、 $D_{i} \geqq P$ となるような時刻 $P$ についての処理を終えた段階で、通れない座標のうち最小のものが $i$ 番目の人が到着する地点になります。
ということで、 $S_{i}-X_{i}$ と $X_{i}$ のペア、もしくは $T_{i}-X_{i}$ と $X_{i}$ のペアに加え、開始か終了かの3つの情報を時刻の昇順にソートしておき、
時刻が若い方から順番に、次に見る $D_{i}$ までの情報を処理していけばよいです。
今どの座標が通れないか、という情報はset等を利用すると簡単に表現できます。

感想

出発地点の時刻に注目する、というのはわかりましたが、それぞれの工事を時刻についての区間、としか見ることができなかったため、考察ができませんでした。逆に、セグ木をきちんと勉強していれば、そのままでも通せた可能性もあるので、どちらにしろ勉強不足だと感じました。
区間を最初と最後に分割する発想、すごいですね…