AtCoder Beginner Contest 183, D : Water Heater

問題文

　https://atcoder.jp/contests/abc183/tasks/abc183_d

問題概要

　給湯器がひとつあり，毎分 $W$ リットルのお湯を出せる．
　給湯器を使いたい人が $N$ 人いて，$i$ 番目の人は時刻 $S_i$ から $T_i$ まで（$T_i$ 丁度は含まない），$P_i$ リットルのお湯を使いたい．お湯は即座に冷めるので溜めておくことはできない．
　全ての人が使いたい量のお湯を使うことはできるか？

制約

• $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$

解法

　お湯を使いたい人々を重み付きの区間だと思うことにします．つまり，$i$ 番目の人とは，重み $P_ｲ$ の半開区間 $[ S_i, T_i )$ です．ここで，任意の時刻についてそこを被覆する区間の重みの合計が $W$ を下回っていれば，答えは Yes になります．
　この判定を愚直に実装すると，時刻ごとに全ての区間を調べる事になってしまい，TLE します．しかし，いもす法 [1] を使うことで前処理 $O( \max\{ T \} )$ 時間で各時刻の情報が $O( 1 )$ 時間でとれるようになります．

参考文献

[1] Kentaro Imajo, "いもす法", https://imoz.jp/algorithms/imos_method.html

コード

int main()
{
	IN( int, N, W );
	VI S( N ), T( N ), P( N );
	REP( i, N )
	{
		cin >> S[i] >> T[i] >> P[i];
	}

	VT< LL > psum( 1 << 18 );
	REP( i, N )
	{
		psum[ S[i] ] += P[i];
		psum[ T[i] ] -= P[i];
	}
	partial_sum( ALL( psum ), begin( psum ) );

	cout << ( *max_element( ALL( psum ) ) <= W ? "Yes" : "No" ) << endl;

	return 0;
}