Overview

Given \(M\) operations that each reduce durability across an interval \([L_j, R_j]\), count the number of streetlights whose durability remains \(1\) or more after all operations.

Analysis

Each blizzard is an operation that “adds (here, subtracts) the same value \(D_j\) to all elements in a contiguous interval.” Naively updating all streetlights in the interval for each blizzard would be \(O(NM)\) in the worst case (since \(N, M \le 2\times 10^5\), this is up to about \(4\times 10^{10}\) operations), which is clearly too slow.

The key observations are:

• All we ultimately need is the total decrease \(\sum D_j\) that each streetlight \(i\) receives (over all \(j\) where \(i \in [L_j, R_j]\)).
• Since each blizzard is a range addition, we can efficiently process the cumulative range additions using a difference array (imos method).

For example, to add \(+3\) to the interval \([2, 4]\) (imagine building up the total decrease): - Add \(+3\) to diff[2] - Add \(-3\) to diff[5] (cancel the effect once we leave the interval)

Then taking prefix sums from left to right reconstructs an array where exactly the elements in the interval have \(+3\) added.

With this method, each blizzard is reflected in \(O(1)\), and at the end we obtain the total decrease for each streetlight in \(O(N)\).

Algorithm

1. Read the initial durability array \(H\) from input.
2. Prepare a difference array diff of length \(N+1\) (to safely compute prefix sums later).
3. For each blizzard \((L, R, D)\), do the following (converting to 0-indexed):
   • diff[L-1] += D
   • If \(R < N\), then diff[R] -= D (If \(R\) is the last element, the cancellation position is outside the array, so it’s unnecessary.)
4. Compute the prefix sum dec of diff from left to right, and for each streetlight \(i\), calculate the final durability as $\(H_i - dec\)\( If this is \)1$ or more, add it to the answer.
5. Output the counted number.

※ As stated in the problem, even if a streetlight collapses midway, the decrease does not stop, so it suffices to look only at the “total decrease at the end.”

Complexity

• Time complexity: \(O(N + M)\) (reflecting blizzards is \(O(M)\), prefix sums and checks are \(O(N)\))
• Space complexity: \(O(N)\) (for the difference array diff and the durability array)

Implementation Notes

• Be careful about update positions in the difference array: Converting the interval \([L, R]\) (1-indexed) to 0-indexed, the start becomes L-1 and the cancellation position becomes R.

• Making diff length \(N+1\) ensures safe boundary handling (in this code, the cancellation is only applied when R < N).

• The decrease and durability values can be up to \(10^9\), and with many operations the prefix sums can grow large, but Python’s int does not overflow.

• For fast I/O, sys.stdin.buffer.read() is used to read all input at once.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)

    H = [next(it) for _ in range(N)]
    diff = [0] * (N + 1)

    for _ in range(M):
        L = next(it)
        R = next(it)
        D = next(it)
        diff[L - 1] += D
        if R < N:
            diff[R] -= D

    dec = 0
    ans = 0
    for i in range(N):
        dec += diff[i]
        if H[i] - dec >= 1:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.