Overview

Given the initial battery levels of \(N\) smartphones, we perform \(Q\) operations that each decrease the battery level by \(1\) for all smartphones in a specified range \([L, R]\), then find the final battery levels. However, battery levels cannot go below \(0\).

Discussion

Naive Approach

For each notification event, we could decrease the value of every smartphone in the range \([L, R]\) by \(1\). However, this method requires up to \(N\) updates per event. The worst-case time complexity is \(O(NQ)\), and with the given constraints (\(N, Q \leq 2 \times 10^5\)), this would require approximately \(4 \times 10^{10}\) operations, which will not fit within the time limit (TLE).

Considering an Efficient Approach

The key observations for this problem are the following two points: 1. The decrease amount is always \(1\): The amount decreased in each event is fixed. 2. Handling “cannot go below \(0\)”: Instead of checking whether the value is \(0\) at each event and updating accordingly, if we know the total number of times each smartphone was decreased, we can compute “initial value \(-\) total decrease count” at the end and set the result to \(0\) if it is negative. This gives the correct answer.

Therefore, this problem can be rephrased as “efficiently counting how many notification events each smartphone was included in”.

Using the Imos Method (Difference Array Technique)

When performing bulk additions (in this case, counting the number of notifications) over a specific range \([L, R]\), the “imos method (difference array technique)” is extremely effective. - Prepare a difference array diff of length \(N+1\). - Replace the operation of adding \(1\) to the range \([L, R]\) with two point updates: diff[L] += 1 and diff[R+1] -= 1. - After processing all queries, compute the prefix sum from left to right to obtain the final cumulative addition (notification count) at each position in \(O(N+Q)\).

Algorithm

1. Initialize an array diff of length \(N+2\) with \(0\).
2. For each of the \(Q\) notification events \([L_i, R_i]\), do the following:
   • diff[L_i] += 1
   • diff[R_i + 1] -= 1
3. Initialize a variable current_events (current prefix sum) to \(0\), and iterate through smartphone numbers \(i = 1\) to \(N\) in order, repeating the following:
   • current_events += diff[i]
   • Compute the final battery level of the \(i\)-th smartphone as \(\max(0, S_i - current\_events)\).
4. Output all computed results.

Complexity

• Time Complexity: \(O(N + Q)\)
  • Reading input takes \(O(N + Q)\), the imos method addition operations take \(O(Q)\), and computing the prefix sum and final battery levels takes \(O(N)\).
• Space Complexity: \(O(N)\)
  • The array for storing initial battery levels and the difference array for the imos method use \(O(N)\) memory.

Implementation Notes

• Large amounts of I/O: In Python, repeatedly calling input() or print() is slow, so we speed things up by reading all input at once with sys.stdin.read().split() and writing all output at once with sys.stdout.write().

• Index handling: The problem uses \(1\)-indexed numbering (starting from 1), so care must be taken with array indexing in the program and avoiding out-of-bounds access (from R+1).

  Source Code

import sys

def main():
    # 標準入力からすべてのデータを取得し、スペース区切りで分割します
    # 大量の入力を処理するため、sys.stdin.read().split() を使用します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # スマートフォンの初期バッテリー残量
    S = list(map(int, input_data[2:N+2]))
    
    # いもす法（imos法）を用いて、各スマートフォンが何回の通知イベントに含まれるかを計算します
    # diff配列は、各インデックスでの変化量を記録します
    diff = [0] * (N + 2)
    
    # 通知イベントの読み込みと差分配列の更新
    idx = N + 2
    for _ in range(Q):
        L = int(input_data[idx])
        R = int(input_data[idx+1])
        diff[L] += 1
        diff[R+1] -= 1
        idx += 2
        
    # 各スマートフォンの最終的なバッテリー残量を計算します
    # 各イベントで減少する量は 1 であり、0 未満にはならないため、
    # 最終的な減少量は「カバーされたイベントの総数」と「初期残量」の小さい方になります
    ans = [0] * N
    current_events = 0
    for i in range(N):
        # 累積和をとることで、i番目のスマートフォンがカバーされた回数を求めます
        current_events += diff[i+1]
        
        # 残量 = 初期値 - 通知回数（ただし 0 未満にはならない）
        res = S[i] - current_events
        if res < 0:
            res = 0
        ans[i] = res
        
    # 結果をスペース区切りで出力します
    sys.stdout.write(" ".join(map(str, ans)) + "\n")

if __name__ == "__main__":
    main()

---

This editorial was generated by gemini-3-flash-preview.