Overview

Given multiple queries that water specific intervals, determine for each flower whether the total amount of water exceeds its threshold.

Analysis

In this problem, there are up to \(2 \times 10^5\) flowers and the same number of watering operations. If we naively add water to every position in the interval for each query, the worst-case time complexity becomes \(O(NM)\), which will not fit within the time limit (TLE).

To efficiently handle uniform addition over intervals, the “difference array (imos method)” is effective. Using a difference array, the operation of adding a value \(W\) to the interval \([L, R]\) can be done in \(O(1)\), and by taking the prefix sum at the end, we can obtain the actual value for each element.

Specifically, prepare an array diff of size \(N+1\), and to add \(W\) to the interval \([L, R]\):

diff[L] += W
diff[R+1] -= W

Then, by taking the prefix sum of diff, we obtain the actual amount of water given to each flower.

Finally, for each flower, check whether the “amount of water given” exceeds the “required water amount \(S_i\)”, and count the number of flowers that exceed it to get the answer.

Algorithm

1. Read input efficiently and obtain the required water amounts \(S_i\) for flowers and the watering queries.
2. Initialize the difference array diff with size \(N+1\).
3. For each watering query \(L_j, R_j, W_j\):
   • Convert to 0-indexed, then perform diff[L] += W, diff[R+1] -= W.
4. Compute the prefix sum of diff to obtain the actual water amount water[i] given to each flower.
5. For each flower, increment the count if water[i] > S[i].
6. Output the count result.

Complexity

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

Implementation Notes

• Correctly convert interval indices from 1-indexed to 0-indexed (subtract 1 from each of \(L_j\) and \(R_j\)).

• Set the size of the difference array to \(N+1\) to prevent out-of-bounds access.

• The final prefix sum can be written concisely using itertools.accumulate.

  Source Code

import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    S = [0] * N
    for i in range(N):
        S[i] = int(data[idx])
        idx += 1
    
    # 差分配列を用意
    diff = [0] * (N + 1)
    
    for _ in range(M):
        L = int(data[idx])
        idx += 1
        R = int(data[idx])
        idx += 1
        W = int(data[idx])
        idx += 1
        
        # 1-indexed -> 0-indexed
        L -= 1
        R -= 1
        
        diff[L] += W
        diff[R + 1] -= W
    
    # 累積和で実際の水量を計算
    water = list(accumulate(diff[:-1]))
    
    # 根腐れをカウント
    count = 0
    for i in range(N):
        if water[i] > S[i]:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

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