Overview

This problem asks us to process \(M\) range addition queries on \(N\) flower beds, then count how many flower beds have a moisture level of at least \(K\). We solve it efficiently using the imos method (difference array).

Analysis

Problems with the Naive Approach

If we naively update all flower beds in the range for each watering operation, each watering requires up to \(O(N)\) updates. Repeating this \(M\) times results in \(O(NM)\) total time complexity. When \(N, M\) are at most \(2 \times 10^5\), this leads to approximately \(4 \times 10^{10}\) operations, causing TLE (Time Limit Exceeded).

Key Insight

This problem involves performing multiple “uniformly add a value to a range” operations. For such problems, the imos method (difference array) is effective.

The basic idea of the imos method is as follows: - Instead of adding value \(z\) to range \([l, r]\), we update the difference array \(diff\) as: - Add \(+z\) to \(diff[l]\) (start adding here) - Add \(-z\) to \(diff[r+1]\) (stop adding here) - Finally, taking the prefix sum of the difference array gives us the total added value at each position

Concrete Example

For \(N = 5\) flower beds, adding moisture \(3\) to range \([2, 4]\):

Initial difference array: [0, 0, 0, 0, 0, 0]  (size N+1)
After operation:          [0, +3, 0, 0, -3, 0]
                             ↑position 2    ↑position 5 (=4+1)

Calculate prefix sum:     [0, 3, 3, 3, 0, 0]
→ We can see that 3 was added to flower beds 2, 3, 4

Algorithm

1. Initialize a difference array \(diff\) of size \(N+1\) with \(0\)
2. For each watering operation \((X_j, Y_j, Z_j)\):
   • Add \(Z_j\) to \(diff[X_j - 1]\) (convert to 0-indexed)
   • Subtract \(Z_j\) from \(diff[Y_j]\)
3. While calculating the prefix sum of the difference array, for each flower bed \(i\):
   • Count if initial moisture \(L_i\) + added moisture \(\geq K\)
4. Output the count

Complexity

• Time Complexity: \(O(N + M)\)

  • Recording to difference array: \(O(1)\) per operation × \(M\) times = \(O(M)\)
  • Prefix sum calculation and counting: \(O(N)\)

• Space Complexity: \(O(N)\)

  • Difference array size: \(N + 1\)

Implementation Notes

1. Index Conversion: The problem uses 1-indexed flower bed numbers, but arrays are 0-indexed, so conversion is needed. \(X_j\) becomes \(X_j - 1\), and \(Y_j\) stays as \(Y_j\) (since it’s the position after the end).

2. Difference Array Size: To prevent out-of-bounds access when subtracting at range endpoints, we set the size to \(N + 1\).

3. Overflow Prevention: In Python, there’s no need to worry about integer overflow, but in languages like C++, the total moisture can become large, so you need to use the long long type.

Source Code

def main():
    import sys
    input = sys.stdin.readline
    
    N, M, K = map(int, input().split())
    L = list(map(int, input().split()))
    
    # Use difference array (imos method)
    # diff[i] represents the change in increment at position i
    diff = [0] * (N + 1)
    
    for _ in range(M):
        X, Y, Z = map(int, input().split())
        # Convert from 1-indexed to 0-indexed
        diff[X - 1] += Z
        diff[Y] -= Z
    
    # Calculate prefix sum to get total watering amount for each flower bed
    water_added = 0
    count = 0
    
    for i in range(N):
        water_added += diff[i]
        if L[i] + water_added >= K:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.