Overview

Given \(N\) flowers, we perform \(M\) range updates (watering operations) and count the number of flowers whose final total water amount exceeds their respective tolerance limit \(S_i\).

Analysis

First, let’s consider a straightforward simulation approach. For each watering operation, if we add the water amount to every flower in the range \([L_j, R_j]\), the worst case (e.g., when all operations cover the entire range) requires \(O(N \times M)\) computation. Given the constraints \(N, M \le 2 \times 10^5\), the number of operations can reach up to \(4 \times 10^{10}\), which will not fit within the time limit.

Therefore, we need a technique to efficiently perform range additions. For problems like this, where we only need to reference the final values after all updates are complete, it is optimal to use the imos method (difference array with prefix sums).

Algorithm

Optimization Using the Imos Method

Using the imos method, each watering operation can be processed in \(O(1)\).

1. Prepare the difference array: Initialize an array diff of length \(N+2\) with \(0\).
2. Update processing: For each operation \((L_j, R_j, W_j)\), update only the following \(2\) positions:
   • diff[L_j] += W_j
   • diff[R_j + 1] -= W_j
3. Compute the prefix sum: After all operations are complete, compute the prefix sum of diff.
   • current_total_water = diff[1] + diff[2] + ... + diff[i] This current_total_water represents the total amount of water flower \(i\) has received.
4. Judgment: For each flower \(i\), if current_total_water > S_i, count it as “root rot”.

Complexity

• Time complexity: \(O(N + M)\)
  • Reading input: \(O(N + M)\)
  • \(M\) update operations: \(O(M)\)
  • Prefix sum computation and judgment: \(O(N)\) Overall \(O(N + M)\), which runs sufficiently fast under the given constraints.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the required water amounts \(S\) and the difference array diff.

Implementation Notes

• Fast I/O: When processing input on the order of \(10^5\) in Python, repeatedly calling input() can be slow. By reading all input at once using sys.stdin.read().split(), the execution time can be significantly reduced.

• Index management: The problem uses 1-indexed notation (flower \(1\) through flower \(N\)), so be careful with array indexing in your program. In this solution, by allocating the diff array with size \(N+2\), we can safely operate on diff[L] and diff[R+1] for a 1-indexed range \([L, R]\).

• Overflow: Since Python has no limit on integer size, even cases where the total water amount exceeds \(10^{14}\) (e.g., \(M=2 \times 10^5, W=10^9\)) can be computed without any special handling.

  Source Code

import sys

def solve():
    # 全ての入力を一度に読み込み、空白で分割して整数のリストに変換します。
    # これにより、大量の入力を高速に処理できます。
    try:
        input_data = sys.stdin.read().split()
        if not input_data:
            return
        data = list(map(int, input_data))
    except EOFError:
        return

    # N: 花の株数, M: 水やり作業の回数
    N = data[0]
    M = data[1]
    
    # S: 各花の必要水分量（許容限界量）
    # 花 i の限界量は S[i-1] に格納されます。
    S = data[2 : 2 + N]
    
    # いもす法（累積和）のための差分配列を準備します。
    # 花の番号は 1 から N なので、サイズ N + 2 の配列を使用します。
    diff = [0] * (N + 2)
    
    # M 回の水やり作業を処理します。
    # 各作業 j では範囲 [L_j, R_j] に水量 W_j を加えます。
    ptr = 2 + N
    for _ in range(M):
        l = data[ptr]
        r = data[ptr + 1]
        w = data[ptr + 2]
        # 差分配列の更新
        diff[l] += w
        diff[r + 1] -= w
        ptr += 3
        
    rotted_count = 0
    current_total_water = 0
    
    # 差分配列から累積和を計算し、各花が受けた水の総量を求めます。
    for i in range(N):
        # i 番目の花（1-indexed で i+1 番目）の総水量を計算
        current_total_water += diff[i + 1]
        
        # 総水量が許容限界量 S_i を超えているか判定します。
        if current_total_water > S[i]:
            rotted_count += 1
            
    # 「根腐れ」を起こした花の総数を出力します。
    sys.stdout.write(str(rotted_count) + '\n')

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.