Overview

Given \(N\) smartphones and \(Q\) range decrease queries, the problem asks to find the remaining battery level of each smartphone after processing all queries.

Analysis

Key Insight

In this problem, there is a constraint that battery levels cannot go below \(0\). However, upon careful consideration, if we know “how many notifications each smartphone received,” the final battery level can be calculated using the following formula:

\[\text{Final Level} = \max(0, \text{Initial Level} - \text{Number of Notifications})\]

This satisfies the condition that the level decreases by \(1\) with each notification and cannot go below \(0\).

Problems with the Naive Approach

If we naively decrease all elements in the interval \([L, R]\) by \(1\) for each query, a single query requires up to \(O(N)\) computations. With \(Q\) queries, the total becomes \(O(NQ)\), and when \(N, Q\) are at most \(2 \times 10^5\), this requires up to \(4 \times 10^{10}\) operations, resulting in TLE.

Solution: imos Method

To efficiently process range addition queries, we use the imos method. With the imos method, we can process all queries in \(O(Q)\) and then compute the effect on each position in \(O(N)\).

Algorithm

How the imos Method Works

The imos method replaces an addition on interval \([L, R]\) with the following two operations:

1. Record \(+1\) at position \(L\)
2. Record \(-1\) at position \(R+1\)

After processing all queries, taking the cumulative sum of the array gives us the number of additions at each position.

Concrete Example

For \(N = 5\) with queries \([2, 4]\) and \([3, 5]\):

Initial array:  [0, 0, 0, 0, 0, 0]  (using index 1~5)
          
Query[2,4]: +1 at index 2, -1 at index 5
Array:      [0, +1, 0, 0, -1, 0]

Query[3,5]: +1 at index 3, -1 at index 6
Array:      [0, +1, +1, 0, -1, -1]

Cumulative sum: [0, 1, 2, 2, 1, 0]

From the cumulative sum result, we can see that position \(2\) receives \(1\) notification, positions \(3, 4\) receive \(2\) notifications, and position \(5\) receives \(1\) notification.

Processing Flow

1. Prepare a difference array imos, and for each query \((L, R)\), execute imos[L] += 1, imos[R+1] -= 1
2. Take the cumulative sum to calculate the notification count notifications[i] for each position
3. Calculate the final battery level for each smartphone \(i\) as \(\max(0, S_i - \text{notifications}[i])\)

Complexity

• Time Complexity: \(O(N + Q)\)
  • Query processing: \(O(Q)\)
  • Cumulative sum calculation: \(O(N)\)
  • Final result calculation: \(O(N)\)
• Space Complexity: \(O(N)\)
  • Uses \(O(N)\) memory for the difference array and notification count array

Implementation Notes

• Be careful with 1-indexed to 0-indexed conversion. The problem statement uses 1-indexed, while Python arrays are 0-indexed, so handle the mapping appropriately
• The imos array accesses index \(R+1\), so allocate a size of at least \(N+2\)
• If you forget max(0, ...), the battery level may become negative, so be careful

Source Code

import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    S = list(map(int, input().split()))
    
    # Manage events for each position
    # start[i]: List of events starting at position i (stores end positions)
    # Calculate how many notifications reach each position using imos method
    imos = [0] * (N + 2)
    
    for _ in range(Q):
        L, R = map(int, input().split())
        imos[L] += 1
        imos[R + 1] -= 1
    
    # Take cumulative sum to calculate notification count for each position
    notifications = [0] * (N + 1)
    current = 0
    for i in range(1, N + 1):
        current += imos[i]
        notifications[i] = current
    
    # Calculate final battery level for each smartphone
    result = []
    for i in range(N):
        # i-th smartphone (i+1 in 1-indexed)
        final_battery = max(0, S[i] - notifications[i + 1])
        result.append(final_battery)
    
    print(' '.join(map(str, result)))

if __name__ == '__main__':
    main()

---

This editorial was generated by claude4.5opus.