Overview

For each interval \([L,R]\), the operation “decrease all elements in that interval by \(1\)” is performed \(Q\) times. We need to efficiently count how many times each smartphone is decreased in total, then output \(S_i - \text{count}\) rounded so it doesn’t go below \(0\).

Analysis

Key Insight

The final remaining battery of each smartphone \(i\) is simply: - Let \(c_i\) be “how many events include smartphone \(i\)” - The final value is \(S_i' = \max(0,\, S_i - c_i)\)

The key point is that regardless of the order of events or whether the value reached \(0\) midway, for the final result we only need to subtract the total number of decreases from \(S_i\) and clamp at \(0\) (since the value cannot go below \(0\)).

Why the Naive Solution Is Too Slow

If we scan the entire interval \([L,R]\) for each event and decrease by \(1\), the worst case is: - \(O(N)\) per event - \(O(NQ)\) for \(Q\) events

This is too slow when \(N, Q \le 2 \times 10^5\).

How to Solve It

All we need is “how many times each position is included in an interval update,” so we use a difference array (imos method) to process range additions efficiently, computing each \(c_i\) in \(O(N+Q)\).

Algorithm

Prepare a difference array diff of length \(N+1\). For each event \([L,R]\) (1-indexed, both endpoints inclusive), process as follows (converting to 0-indexed):

• Let \(L' = L-1\), then
  diff[L'] += 1
• To cancel the effect starting from the position after the right endpoint, if \(R\) is less than \(N\):
  diff[R] -= 1
  (Here R is the 1-indexed right endpoint, so in 0-indexed terms it corresponds to the position “one past the right endpoint”)

Then, compute the prefix sum cur from left to right: - cur += diff[i] gives \(c_i = cur\) - The final value is S[i] = max(0, S[i] - cur)

Concrete Example

Suppose \(N=5\) and there is only one event \([2,4]\). - diff[1] += 1 (decrease starts from the 2nd element) - diff[4] -= 1 (the next position after the 4th = the 5th element is not decreased)

The prefix sum of diff becomes [0,1,1,1,0], showing that only the 2nd through 4th elements are decreased once.

Complexity

• Time complexity: \(O(N+Q)\) (difference array updates \(Q\) times, prefix sum \(N\) times)
• Space complexity: \(O(N)\) (difference array)

Implementation Notes

• The input \([L,R]\) is 1-indexed, so convert the left endpoint to 0-indexed by L -= 1.

• diff[R] -= 1 should only be done when \(R < N\) (to prevent out-of-bounds access).

• The final value should use max(0, ...) to ensure it doesn’t go below \(0\).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    S = list(map(int, input().split()))
    diff = [0] * (N + 1)

    for _ in range(Q):
        L, R = map(int, input().split())
        L -= 1
        diff[L] += 1
        if R < N:
            diff[R] -= 1

    cur = 0
    for i in range(N):
        cur += diff[i]
        v = S[i] - cur
        S[i] = v if v > 0 else 0

    sys.stdout.write(" ".join(map(str, S)))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.