Overview

Given \(N\) flowers, we perform \(M\) “range additions (growth over specific ranges)” and count the number of flowers whose final height reaches or exceeds their respective target value \(T_i\).

Analysis

Naive Approach and Its Limitations

The first idea that comes to mind is to update the height of each individual flower in the specified range \([L_j, R_j]\) for each day’s watering. However, since a single watering can update up to \(N\) flowers, the overall time complexity becomes \(O(N \times M)\). Given the constraints of this problem, \(N, M \leq 2 \times 10^5\), this would require up to about \(4 \times 10^{10}\) operations, far exceeding the time limit (typically around 2 seconds).

Efficient Update Strategy

In this problem, only the “final height after all watering is done” matters. There is no need to check intermediate heights along the way. For cases like this, where multiple range additions are applied and only the final result is needed, the “imos method (difference array)” technique is extremely effective.

Algorithm

Imos Method (Difference Array)

Using the imos method, the operation of adding value \(W\) to the range \([L, R]\) can be accomplished by updating just 2 positions at the endpoints of the array.

1. Prepare a difference array diff of length \(N+1\), initialized entirely to \(0\).
2. For each day’s watering \((L_j, R_j, W_j)\), update as follows:
   • diff[L_j - 1] += W_j (add at the start of the range)
   • diff[R_j] -= W_j (subtract at the position right after the end of the range)
3. After all watering is done, compute the prefix sum of diff from left to right.
   • If current_growth = diff[0] + diff[1] + ... + diff[i], then this current_growth is the total growth of flower \(i+1\).
4. For each flower, check whether “initial height \(H_i\) + total growth \(\geq\) target height \(T_i\)”, and count those that satisfy the condition.

With this technique, each watering operation is processed in \(O(1)\), and the final aggregation takes only \(O(N)\), resulting in a dramatic speedup.

Complexity

• Time Complexity: \(O(N + M)\)
  • Reading input: \(O(N + M)\)
  • Processing \(M\) watering operations (imos method): \(O(M)\)
  • Computing final heights via prefix sum and checking conditions: \(O(N)\)
• Space Complexity: \(O(N + M)\)
  • Arrays to store flower information and watering information use \(O(N + M)\) memory.

Implementation Notes

• Fast I/O: In Python, repeatedly calling input() is slow, so the standard practice is to read all input at once using sys.stdin.read().split().

• Index Adjustment: The problem uses 1-indexed numbering (starting from 1), but arrays in programs are typically 0-indexed (starting from 0). Care must be taken with the handling of L-1 and R.

• Large Numbers: Since the target height \(T_i\) can be as large as \(10^{18}\), the total growth can also become very large. Python natively supports arbitrary-precision integers, so there is no concern about overflow.

  Source Code

import sys

# 競技プログラミング用の高速な入出力とアルゴリズム
def solve():
    # 全ての入力を一度に読み込み、空白で分割してリストにする
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 全ての文字列を整数に一括変換する（ループ内で変換するより高速）
    all_ints = list(map(int, input_data))
    
    # N: 花の本数, M: 水やりの日数
    N = all_ints[0]
    M = all_ints[1]
    
    # H: 各花の初期の高さ
    # T: 各花の目標の高さ
    # スライスを用いてリストを抽出
    H = all_ints[2 : N + 2]
    T = all_ints[N + 2 : 2 * N + 2]
    
    # いもす法（差分配列）を用いて区間加算を効率的に行う
    # diff[i] は i 番目の花からの成長量の変化を表す
    # 花の番号は 1 から N なので、0-indexed に直してサイズ N+1 の配列を用意
    diff = [0] * (N + 1)
    
    # 水やり情報の開始インデックス
    start_idx = 2 * N + 2
    # M 日間の水やりを処理
    for j in range(M):
        # 各日の情報: L (左端), R (右端), W (伸びる高さ)
        idx = start_idx + 3 * j
        L = all_ints[idx]
        R = all_ints[idx + 1]
        W = all_ints[idx + 2]
        
        # 1-indexed の区間 [L, R] を 0-indexed に変換して差分配列を更新
        diff[L - 1] += W
        diff[R] -= W
        
    # 十分に成長した花の本数をカウント
    count = 0
    current_growth = 0
    # 差分配列の累積和をとることで、各花の最終的な合計成長量を求める
    for i in range(N):
        current_growth += diff[i]
        # 最終的な高さ = 初期高さ + 合計成長量
        # これが目標高さ T[i] 以上であればカウント
        if H[i] + current_growth >= T[i]:
            count += 1
            
    # 結果を出力
    sys.stdout.write(str(count) + '\n')

if __name__ == '__main__':
    solve()

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