AtCoder Beginner Contest 128：E - Roadwork
問題
解法
工事期間を [S_i - X_i, T_i - X_i) とすることで，座標 0 を出発する時間から行き止まりになる座標が分かる形に情報を変形することが出来る．このもとで考える．ここで，今工事中である座標をソートした形で持っておく配列（set などで管理する）を running, これから先の工事開始・工事終了の情報を時間でソートした形で持っておく配列（これも set などで管理する）を events とする．このとき，i 人目が行き止まりになる座標は，時刻 D_i までの events を処理したあと，running の中で最も小さい座標となる．events 内では（工事開始か終了が起きる時刻，座標，開始か終了か）という形で管理しておく．時刻 D_i までの events の中で，開始のイベントであれば，工事が行われる座標を running に追加し，終了のイベントであれば反対に削除する．これを D_i を進めながら同時に行っていくことで，各 D_i について答えが O(logN) で求めることが出来る．全体で O((N + Q) logN)．
解答
