Calculating the amount of use of hot water directly needs \(O(N)\) time for each time period, so the total time complexity will be \(O(NT)\), where \(T\) is the maximum time period (\(2\times 10^5\)), which does not finish in time limit.

Intuitively, it seems to be good idea to run a simulation like “the amount of water usage increases by \(P_i\) at time \(S_i\), and decreases by \(P_i\) at time \(T_i\).” Actually you can do the simulation by sorting by \(S_i\) and \(T_i\) to solve the problem in a total of \(O(N\log N)\) time, but this time, as the maximum time period is small enough, we can solve it in a total of \(O(N+T)\) time using cumulative sums, which is easier to implement.

Prepare an array \(a\) initialized with \(0\). For each \(i\), let

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

then take the cumulative sum of the array \(a\), then the amount of water usage at time \(X\) is \(a[X]\). Now we can check if the maximum value of this array exceeds \(M\).

Sample Code (C) with cumulative sum

Sample Code (C++) by simulation