Overview

There are \(N\) streetlights, each with an initial durability value. Over \(M\) blizzards, the durability of streetlights belonging to each interval decreases. After all blizzards have ended, find the number of streetlights with durability of 1 or more.

Analysis

In this problem, if we naively reduce the durability of streetlights in the interval \([L_j, R_j]\) for each blizzard, the worst-case time complexity becomes \(O(N \cdot M)\), which is too slow for the constraints \(N, M \leq 2 \times 10^5\) (it will TLE).

The key observation is that we only need the total sum of damage from blizzards for each streetlight, and intermediate states are unnecessary. Therefore, if we have a method to efficiently process range additions, we can speed things up.

This leads us to consider using a difference array. This is a technique where an operation of adding a constant value to a range can be processed in \(O(1)\) by recording the value only at the start and end+1 positions of the array. Afterward, taking the prefix sum gives us the result of additions for each element.

For example, with \(N=5\) streetlights, consider a blizzard dealing \(D=3\) damage to the interval \([2, 4]\):

• For the difference array diff:
  • diff[1] += 3 (the 2nd element in 0-indexed)
  • diff[4] -= 3 (the 5th element in 0-indexed; if it doesn’t exist, we extend to the outside)
• Taking the prefix sum reflects \(3\) in the interval \([1, 3]\) (0-indexed)

In this way, we efficiently process the range subtraction for each blizzard, and take the prefix sum just once at the end to compute the total damage for each streetlight.

Algorithm

1. Read the initial durability array \(H\).
2. Prepare a difference array diff of length \(N+1\) (initialized to 0).
3. For each blizzard:
   • To add \(D_j\) damage to the interval \([L_j, R_j]\):
     • diff[L_j - 1] += D_j
     • diff[R_j] -= D_j
4. Take the prefix sum of the difference array to obtain the total damage damages for each streetlight.
5. For each streetlight, compute the final durability \(H[i] - damages[i]\), and increment the count if it is 1 or more.
6. Output the count.

Complexity

• Time complexity: \(O(N + M)\)
  Each blizzard is processed in constant time, and the final prefix sum and evaluation take \(O(N)\).
• Space complexity: \(O(N)\)
  \(O(N)\) is needed for the difference array and damage array.

Implementation Notes

• Since blizzard intervals are given in 1-indexed form, convert to 0-indexed when accessing arrays (i.e., use \(L-1\) and \(R\)).

• By making the difference array of size \(N+1\), the right-end update diff[R] -= D can be performed safely.

• When taking the prefix sum at the end, use only the portion up to diff[:-1] (excluding the extra element at the end).

  Source Code

import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    H = list(map(int, data[idx:idx+N]))
    idx += N
    
    # 差分配列を用意
    diff = [0] * (N + 1)
    
    for _ in range(M):
        L = int(data[idx])
        idx += 1
        R = int(data[idx])
        idx += 1
        D = int(data[idx])
        idx += 1
        
        diff[L-1] += D
        diff[R] -= D
    
    # 累積和で各区間への減少量を求める
    damages = list(accumulate(diff[:-1]))
    
    # 各街灯の最終耐久値を計算し、1以上か判定
    count = 0
    for i in range(N):
        final_health = H[i] - damages[i]
        if final_health >= 1:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

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