各時刻で使われているお湯の量を直接求めようとすると \(O(N)\) かかるため、時刻の最大値 (\(2\times 10^5\)) を \(T\) として時間計算量 \(O(NT)\) となり、実行時間制限に間に合いません。

直感的には「時刻 \(S_i\) になったらお湯の使用量が \(P_i\) 増え、時刻 \(T_i\) になったら\(P_i\) 減る」としてシミュレーションをすると良さそうです。実際に、\(S_i, T_i\) でソートすることでシミュレーションすることで \(O(N\log N)\) で解くこともできますが、今回は時刻の最大値が小さいことを利用して、 いもす法 により \(O(N+T)\) で解く方法の方が実装が容易です。

\(0\) で初期化された配列 \(a\) を用意します。各 \(i\) に対し、

• \(a[S_i] \leftarrow a[S_i]+P_i\)
• \(a[T_i] \leftarrow a[T_i]-P_i\)

としたのち、配列 \(a\) の累積和を取ると、時刻 \(X\) に使われるお湯の量が \(a[X]\) になります。この配列の最大値が \(W\) 以下であるかどうかを調べればよいです。

回答例(C) いもす法

回答例(C++) シミュレーション