Overview

Given \(N\) flower beds, we perform \(M\) operations where each operation adds moisture \(Z_j\) to a specified range \([X_j, Y_j]\). The problem asks us to find the number of flower beds whose final moisture level is at least \(K\).

Analysis

First, let’s consider a naive approach (simulation). For each watering operation, if we loop from flower bed \(X_j\) to \(Y_j\) and add the moisture, a single watering operation may require up to \(N\) additions. Since watering is performed \(M\) times, the overall time complexity is \(O(NM)\). Looking at the constraints, \(N, M \leq 2 \times 10^5\), so \(N \times M\) can be up to \(4 \times 10^{10}\), which will not fit within the time limit.

To efficiently perform range updates, we use the “imos method (difference array)”. Using the imos method, an addition operation on range \([X, Y]\) can be converted into an \(O(1)\) operation that only updates two positions in the array. After all operations are completed, by taking a prefix sum, we can compute the final accumulated value at each position in \(O(N)\).

Algorithm

Steps of the imos method

1. Prepare a difference array diff of length \(N+2\), initialized entirely to \(0\).
2. For each watering operation \((X_j, Y_j, Z_j)\), update as follows:
   • Add \(Z_j\) to diff[X_j]
   • Subtract \(Z_j\) from diff[Y_j + 1]
3. Compute the prefix sum of diff sequentially from \(1\) to \(N\).
   • The prefix sum current_increase at position \(i\) represents the “total moisture increase” at that position.
4. For each position \(i\), check whether the sum of the initial moisture \(L_i\) and the total increase current_increase is at least \(K\), and count accordingly.

Concrete example

For example, suppose there are 3 flower beds (all with initial value 0), and we add \(5\) to the range \([1, 2]\): - diff[1] += 5 - diff[3] -= 5 (the element after index 2) - Taking the prefix sum: - \(i=1\): \(5\) - \(i=2\): \(5 + 0 = 5\) - \(i=3\): \(5 + 0 - 5 = 0\) This correctly adds \(5\) only to the range \([1, 2]\).

Complexity

• Time complexity: \(O(N + M)\)
  • Reading input takes \(O(N + M)\)
  • \(M\) range update operations take \(O(M)\)
  • Prefix sum computation and evaluation take \(O(N)\)
  • Overall, it runs in linear time with respect to \(N\) and \(M\), which is sufficiently fast.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the array \(L\) storing initial values and the difference array diff.

Implementation notes

• Fast I/O: In Python, repeatedly calling input() is slow, so techniques like reading all input at once with sys.stdin.read().split() are effective.

• Array size: Since the difference array accesses index Y_j + 1, allocating the array with size \(N+2\) or so allows implementation without worrying about boundary conditions (such as when \(Y_j = N\)).

• 1-indexed vs 0-indexed: The problem numbers flower beds starting from \(1\), but Python lists start from \(0\). Care must be taken with the index correspondence between the initial value list \(L\) and the difference array diff.

  Source Code

import sys

def solve():
    # 入力を一度に読み込み、空白で分割してトークンのリストを作成します。
    # これはPythonにおいて大量の入力を高速に処理する一般的な手法です。
    data = sys.stdin.read().split()
    if not data:
        return
    
    # イテレータを使用してデータを順番に取得します。
    it = iter(data)
    
    # N: 花壇の数, M: 水やりの回数, K: 水分量の基準値
    N = int(next(it))
    M = int(next(it))
    K = int(next(it))
    
    # 各花壇の初期水分量 L_i を読み込みます。
    L = [int(next(it)) for _ in range(N)]
    
    # いもす法（累積和を用いた範囲更新）のための差分配列を準備します。
    # 花壇の番号は1からNまでなので、サイズは N+2 とします。
    diff = [0] * (N + 2)
    
    # M 回の水やり情報を処理します。
    for _ in range(M):
        # x: 開始花壇, y: 終了花壇, z: 増加する水分量
        x = int(next(it))
        y = int(next(it))
        z = int(next(it))
        
        # 差分配列の更新
        diff[x] += z
        if y + 1 <= N:
            diff[y+1] -= z
            
    # 各花壇の最終的な水分量を計算し、基準値 K 以上であるか判定します。
    ans = 0
    current_increase = 0
    for i in range(1, N + 1):
        # 差分配列の累積和が、その花壇における水分量の合計増加量になります。
        current_increase += diff[i]
        
        # 初期水分量 L[i-1] に増加量を足したものが最終的な水分量です。
        if L[i-1] + current_increase >= K:
            ans += 1
            
    # 結果を出力します。
    print(ans)

if __name__ == '__main__':
    solve()

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