Overview

This is a problem where you perform multiple range addition operations (accumulating damage) and then determine the final state of each element.

Analysis

For each blizzard, we perform an operation that reduces the durability of streetlights in the specified range from \(L_j\) to \(R_j\) by \(D_j\) each.

A naive approach would be to loop through all streetlights from \(L_j\) to \(R_j\) for each blizzard and calculate the damage. However, in this case, a single blizzard can affect up to \(N\) streetlights, resulting in an overall time complexity of \(O(N \times M)\). Given the constraints \(N, M \le 2 \times 10^5\), the worst case would require up to \(4 \times 10^{10}\) operations, which would exceed the time limit (TLE).

We need to efficiently compute the “total damage received by each streetlight” after all blizzards have ended. When performing multiple operations of “adding the same value to a specific range,” using the imos method (difference array and prefix sum) is extremely effective.

Algorithm

We use the “imos method” to calculate the total damage received by each streetlight.

1. Prepare a difference array diff of length \(N+2\), initialized entirely to \(0\).
2. For the \(j\)-th blizzard (damage \(D_j\) to the range \([L_j, R_j]\)), perform the following operations:
   • Add \(D_j\) to diff[L_j] (damage starts here)
   • Subtract \(D_j\) from diff[R_j + 1] (damage ends here)

Concrete example: To deal 5 damage to the range of streetlights 2 through 4, add \(5\) to diff[2] and subtract \(5\) from diff[5]. When we later compute the prefix sum, the values at indices 1, 2, 3, 4, 5 become \(0, 5, 5, 5, 0\) respectively, correctly applying damage to the entire range.

1. After recording the information for all blizzards, compute the prefix sum of the array diff. By calculating current_damage += diff[i] from left to right, current_damage becomes the total damage received by streetlight \(i\).
2. Finally, compare each streetlight’s initial durability \(H_i\) with the total damage. If \(H_i > current\_damage\), the streetlight has not collapsed (it has at least \(1\) durability remaining), so we add \(1\) to the answer.

Complexity

• Time complexity: \(O(N + M)\) Recording to the difference array takes \(O(M)\), and computing the prefix sum and determining survivors takes \(O(N)\), so the overall complexity is \(O(N + M)\). This runs sufficiently fast under the given constraints.
• Space complexity: \(O(N)\) Memory is needed to store the initial durability array and the difference array diff of length \(N+2\).

Implementation Notes

• 1-indexed handling: The problem’s indices start from \(1\). By allocating the array with size \(N+2\), we prevent out-of-bounds access (IndexError) when accessing diff[R+1].

• Fast I/O: In Python, reading standard input can easily become a bottleneck, so we use the technique of reading the entire input at once with sys.stdin.read().split() and parsing it afterward, which significantly reduces execution time.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    H = [int(x) for x in input_data[2:N+2]]
    
    diff = [0] * (N + 2)
    
    idx = N + 2
    for _ in range(M):
        L = int(input_data[idx])
        R = int(input_data[idx+1])
        D = int(input_data[idx+2])
        diff[L] += D
        diff[R+1] -= D
        idx += 3
        
    current_damage = 0
    ans = 0
    for i in range(1, N + 1):
        current_damage += diff[i]
        if H[i-1] > current_damage:
            ans += 1
            
    print(ans)

if __name__ == '__main__':
    main()

---

This editorial was generated by gemini-3.1-pro-thinking.