人権なし

競プロで解いた問題や開発の進捗などの記録です

大手前プロコン 2019:E - 最悪の教頭 (Worst Head Teacher)

問題

https://atcoder.jp/contests/otemae2019/tasks/otemae2019_e

解法

参加者 i は (D_1 - 1) + (D_2 - 1) + ... + (D_i - 1) 秒後に動き始める.これを t_i とおく.なので,参加者 i が座標 1 に到達するのは t_i + (1 + i) 秒後になる.

各クエリの T_i 秒後の区間 [L_i, R_i] を T_i - L_i + 1 秒後の区間 [1, R_i - L_i + 1] として考える.T_i - L_i + 1 秒後にこの区間にいる条件は,座標 1 に到達するのが [T_i -R_i + 1, T_i - L_i + 1] 秒後であるときになる.この区間に含まれる t_i の個数を std::lower_bound(), std::upper_bound() を用いて計算すればよい.O(N + QlogN).

解答

https://atcoder.jp/contests/otemae2019/submissions/6696894

f:id:babcs2035:20190805154915p:plain