AtCoder Beginner Contest 183 D – Water Heater を解いた記録

問題の概要

給湯器が1つあり，毎分\(W\)リットルのお湯を供給できる．

人が\(N\)人いる．人\(i\)は時刻\(S_i\)から\(T_i\)まで（ただし\(T_i\)ちょうどを除く），この給湯器から供給されるお湯を\(P_i\)リットル使おうとしている．
どの時刻においてもお湯の使用量が\(W\)以下となるかを判定せよ．

問題へのリンク

制約

• \(1 \leq N \leq 2 \times 10^{5}\)
• \(0 \leq S_i < T_i \leq 2 \times 10^{5}\)
• \(1 \leq W, P_i \leq 10^{9}\)
• 入力はすべて整数

解法

各時刻におけるお湯の使用量をいもす法で計算して瞬殺です．詳細はいもす法 – いもす研 (imos laboratory)をお読みください．

実装例

感想

この問題は5分程度で解け，AからDまで全部合わせても23分程度で解けました．E問題を解ければ確実に水パフォ以上を取れたのですが，焦って自滅し，結局解けないまま終わってしまいました．
その結果，ABC183は緑パフォになってしまったのでかなり辛いです．80分近く残っていたのだから焦らなくても良かったというのに…