Overview

There are \(N\) smartphones, each with an initial battery level.
There are \(Q\) notification events, and each event decreases the battery of smartphones in a certain interval by 1 (but not below 0).
After all events, determine the battery level of each smartphone.

Analysis

A naive approach to this problem might try to decrease the battery by 1 for each smartphone in the interval \([L, R]\) for every event. However, such a straightforward implementation has a time complexity of \(O(Q \times N)\), which becomes extremely large under the constraints \(N, Q \leq 2 \times 10^5\), resulting in TLE (Time Limit Exceeded).

To efficiently handle the operation of “adding a constant value to an interval,” we use a difference array (imos method).
By using a difference array, we can perform interval updates in \(O(1)\), and then take a prefix sum at the end to quickly compute the total addition for each element.

Specifically, instead of adding 1 to the interval \([L, R]\) for each event, we record \(+1\) at position \(L\) and \(-1\) at position \(R+1\) in the difference array. Then, by taking the prefix sum, we obtain the total decrement for each smartphone.

Finally, we subtract the decrement from the initial battery level and clip the result to be at least 0 to obtain the answer.

Algorithm

1. Read input efficiently (using sys.stdin.read).
2. Prepare a difference array diff of size \(N+1\) (one extra element for boundary handling).
3. For each event:
   • For the interval \([L, R]\), perform diff[L] += 1 and diff[R+1] -= 1 (converting to 0-indexed).
4. Take the prefix sum of the difference array to obtain the decrement decrements for each smartphone.
5. Subtract the decrement from each smartphone’s initial battery level, clip the value to be at least 0, and output the result.

Complexity

• Time complexity: \(O(N + Q)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Convert indices to 0-based (input is 1-based).
• Set the size of the difference array to \(N+1\) to prevent out-of-bounds access.
• The final result should be computed as max(0, S[i] - decrements[i]) to ensure it does not become negative.
• Using fast input processing (sys.stdin.read) allows handling large amounts of input efficiently.

## Source Code

```python
import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    Q = int(data[1])
    
    S = list(map(int, data[2:2+N]))
    
    # 差分配列を用意
    diff = [0] * (N + 1)
    
    index = 2 + N
    for _ in range(Q):
        L = int(data[index]) - 1   # 0-indexedにする
        R = int(data[index+1]) - 1
        diff[L] += 1
        diff[R+1] -= 1
        index += 2
    
    # 差分配列を累積和して、各要素への減少量を求める
    decrements = list(accumulate(diff[:-1]))
    
    # 各スマートフォンの最終バッテリー量を計算
    result = [max(0, S[i] - decrements[i]) for i in range(N)]
    
    print(' '.join(map(str, result)))

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.