Overview

In this problem, we need to efficiently process multiple range addition operations and determine whether the final value of each element is at least a threshold \(K\).

Analysis

First, as a naive approach, we consider directly updating the moisture level of all flower beds in the specified range for each watering operation. However, in the worst case, a single watering operation updates up to \(N\) elements, and this is repeated \(M\) times, resulting in an overall time complexity of \(O(NM)\). Given the constraints \(N, M \leq 2 \times 10^5\), this is not practical (it will TLE).

To efficiently handle uniform additions over ranges, we use a technique called “difference array (imos method).” The idea is to add the increment at the start of the range and subtract it at the position right after the end of the range. Then, by taking the prefix sum at the end, we can obtain the total addition for each element.

For example, to add a moisture level of 10 to flower beds 3 through 5, we set diff[2] += 10 and diff[5] -= 10. After that, taking the prefix sum of diff gives us the actual moisture added to each flower bed.

With this method, each watering operation can be processed in constant time, so the overall time complexity becomes \(O(N + M)\).

Algorithm

1. Read the initial moisture level \(L_i\) for each flower bed.
2. Prepare a difference array diff of size \(N+1\), initialized to 0.
3. For each watering operation, add \(Z_j\) to the range \([X_j, Y_j]\) as follows:
   • diff[X_j - 1] += Z_j
   • diff[Y_j] -= Z_j
4. Compute the prefix sum of diff to obtain the total added moisture delta for each flower bed.
5. Calculate the final moisture level of each flower bed as \(L_i + \text{delta}[i]\), and increment the count if it is at least \(K\).
6. Output the count.

Complexity

• Time complexity: \(O(N + M)\)
• Space complexity: \(O(N)\)

Implementation Notes

• sys.stdin.read is used for fast input reading.

• Since ranges are given in 1-indexed format, they need to be converted to 0-indexed for internal processing.

• The difference array should be of size \(N+1\) to prevent out-of-bounds access at the end.

• Don’t forget to add delta[i] when computing the final moisture level.

  Source Code

import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    
    L = list(map(int, data[3:3+N]))
    
    # 差分更新用の配列
    diff = [0] * (N + 1)
    
    idx = 3 + N
    for _ in range(M):
        X = int(data[idx]) - 1   # 0-indexed
        Y = int(data[idx+1]) - 1
        Z = int(data[idx+2])
        diff[X] += Z
        diff[Y+1] -= Z
        idx += 3
    
    # 差分を累積和して各区間にかかる増加分を計算
    delta = list(accumulate(diff))[:-1]
    
    # 最終的な水分量を計算し、K以上かどうか判定
    count = 0
    for i in range(N):
        final_moisture = L[i] + delta[i]
        if final_moisture >= K:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.