大手前プロコン 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