Overview

We process the \(M\) operations of adding the same amount of water to intervals \([L_j, R_j]\) collectively, and count how many flowers end up receiving a total water amount exceeding \(S_i\).

Analysis

Each watering operation adds the same water amount \(W_j\) to all flowers in a contiguous interval. If we naively “add to every flower in the interval for each operation,” we would need up to \(N \times M \approx 4 \times 10^{10}\) updates in the worst case, which would certainly result in a time limit exceeded.

The key insight here is: “Instead of directly applying interval additions to the array, we only need to record the differences (boundaries of increases and decreases).”

For example, consider \(N=5\) and an operation that adds \(+3\) to the interval \([2,4]\). Instead of directly updating each element, we remember only the “boundaries”:

• The addition starts at position 2 (apply \(+3\) here)
• The addition ends after position 4, i.e., at position 5 (apply \(-3\) here)

Then, by taking the prefix sum from left to right at the end, we can recover the final added amount at each position. This method is commonly known as the “imos method (difference array).”

Algorithm

1. Prepare a difference array diff of length \(N\) (in implementation, size \(N+1\) to simplify boundary handling).
2. For each watering operation \((L, R, W)\) (1-indexed, both endpoints inclusive):
   • diff[L-1] += W (convert to 0-indexed and increment at the start position)
   • diff[R] -= W (decrement at the position after the end. However, if \(R=N\), this would be out of bounds, so we skip it)
3. Take the prefix sum cur of diff from left to right. For each flower \(i\), if the total water amount cur exceeds \(S_i\), add it to the answer.

At this point, the prefix sum cur represents “the total water amount received by that flower (sum of all operations).”

Complexity

• Time complexity: \(O(N + M)\) (Each operation is reflected in the difference array in \(O(1)\), followed by \(N\) prefix sum computations at the end)
• Space complexity: \(O(N)\) (For storing the difference array)

Implementation Notes

• Since the input is \(1\)-indexed, we convert only the start position to \(0\)-indexed by doing L -= 1.

• Adding to an interval \([L, R]\) (both endpoints inclusive) translates in the difference array to “\(+W\) at the start, \(-W\) at the position after the end.” In this code, we perform diff[R] -= W, but when \(R=N\), diff[N] is effectively unnecessary, so we branch with if R < N:.

• Water amounts and required water thresholds can be up to \(10^9\), and the number of operations can be up to \(2\times 10^5\), so the cumulative sum can reach approximately \(2\times 10^{14}\). However, Python’s int handles this safely.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    diff = [0] * (N + 1)

    for _ in range(M):
        L, R, W = map(int, input().split())
        L -= 1
        diff[L] += W
        if R < N:
            diff[R] -= W

    cur = 0
    ans = 0
    for i in range(N):
        cur += diff[i]
        if cur > S[i]:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.