Overview

This is a problem where after performing \(M\) range additions (watering consecutive flower beds), you count the number of flower beds whose final moisture level is at least \(K\).

Analysis

Each watering operation is “add \(Z_j\) to the interval \([X_j, Y_j]\).” A naive approach would be to add to every flower bed in the interval each time, but implementing this directly would result in the worst case of:

• Each watering covers an interval of length \(O(N)\)
• There are \(M\) waterings

giving a total of \(O(NM)\). Given the constraints \(N, M \le 2 \times 10^5\), this could require up to about \(4 \times 10^{10}\) updates, which will certainly result in a time limit exceeded.

The key insight here is that “adding the same value to an entire interval” can be handled by recording only the differences (change points of the increment), and then reconstructing the values all at once using a prefix sum at the end.

For example, when \(N=5\) and we want to add \(+3\) to interval \([2,4]\) (1-indexed): - At position 2, “+3 starts taking effect” - At position 5 (= 4+1), “+3 stops taking effect”

With just this information, we can compute the addition amount at each position by accumulating from left to right.

Algorithm

We use a difference array (the so-called imos method).

1. Read the initial moisture array \(L\) of length \(N\).
2. Initialize the difference array diff (of length \(N+1\) is fine, but in implementation we allocate \(N+1\) while referencing \(0..N-1\)) to 0.
3. For each query (\(X, Y, Z\)), converting to 0-indexed:
   • diff[X] += Z (increase starts here)
   • If Y+1 < N, then diff[Y+1] -= Z (increase ends here)
4. Compute add as a prefix sum from left to right:
   • add += diff[i]
   • The final moisture level is L[i] + add
   • If this is at least \(K\), increment the count
5. Output the count.

By doing this, each interval operation is converted into “updates at just 2 endpoints,” and a single final scan recovers the total increase for all flower beds.

Complexity

• Time complexity: \(O(N + M)\) (difference updates \(M\) times, prefix sum and comparison \(N\) times)
• Space complexity: \(O(N)\) (arrays \(L\) and diff)

Implementation Notes

• The input is 1-indexed, so in the code we convert to x = X-1, y = Y-1.

• diff[y+1] -= z is only performed when y+1 is within the array bounds (if y is the last element, there is no “decrease point”).

• Since \(N, M\) can be large, in Python, fast input methods such as bulk reading with sys.stdin.buffer.read() are effective.

  Source Code

import sys

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

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

    for _ in range(M):
        x = next(it) - 1
        y = next(it) - 1
        z = next(it)
        diff[x] += z
        if y + 1 < N:
            diff[y + 1] -= z

    cnt = 0
    add = 0
    for i in range(N):
        add += diff[i]
        if L[i] + add >= K:
            cnt += 1

    sys.stdout.write(str(cnt))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.