https://atcoder.jp/contests/abc128/submissions/12875865
- std::setのinsertと二分探索、removeが便利。
工事座標Xに到達するのにX秒かかることから逆算する。工事範囲[S-X, T-X)で二分探索してスタート時間Dの人が工事に引っかかる範囲を対応させる。ただし、引っかかる工事が確定した人を積極的に排除していかないと最悪になってしまうため、人のスタート時間Dをsetに格納して削除をで出来るようにしておく。 スタートに近い工事座標で止まるべき人がスタートから離れた工事座標になってしまうと困るので、工事座標昇順にソートして上記処理をする必要がある。
なお、全ての人が1秒で距離1しか歩かないので、予めスタート地点をマイナス方向に調整する方法もあるが、今回はそのまま実装したほうが簡潔になると思われる。