概要

区間 \([L_j, R_j]\) に一括で加算される成長量を全日分まとめて処理し、最終的に目標 \(T_i\) を満たす花の本数を数えます。

考察

各日 \(j\) の水やりは「区間加算」なので、素朴にやると
- 日ごとに区間内の全ての花へ \(W_j\) を足す
となり、最悪で \(O(NM)\)（最大 \(2\times 10^5 \cdot 2\times 10^5\)）になって到底間に合いません。

重要な気づきは、最終的に知りたいのは「各花が合計でいくら伸びたか」だけであり、日ごとの更新を逐一反映する必要はないことです。

そこで、区間加算を高速に集計できる 差分配列（いもす法） を使います。

例として、\(N=5\) に対し区間 \([2,4]\) に \(+3\) を加えたいとき（1-indexed）
- 差分配列 diff に diff[2] += 3, diff[5] -= 3（区間の右端の次）
としておけば、diff の累積和を取った値が各位置の加算量になります。
複数の区間も同様に「端点だけ」記録して、最後に1回の累積和で合計成長量を得られます。

アルゴリズム

1. 長さ \(N\) の差分配列 diff を用意する（実装では扱いやすくするため \(N+1\) 長を確保）。
2. 各日 \(j\) の操作 \((L_j, R_j, W_j)\) について（0-indexに直す）
   
   • diff[L_j] += W_j
     
   • diff[R_j+1] -= W_j（ただし \(R_j+1 < N\) のときのみ。番兵を使うなら常に書いてもよい）
3. diff の累積和 cur を左から計算すると、花 \(i\) の「合計成長量」が得られる。
4. 各花 \(i\) について最終高さ \(H_i + cur\) を計算し、\(H_i + cur \ge T_i\) ならカウントする。
5. カウントを出力する。

計算量

• 時間計算量: \(O(N + M)\)（区間情報の反映 \(M\) 回 + 累積和と判定 \(N\) 回）
• 空間計算量: \(O(N)\)（差分配列）

実装のポイント

• 入力は \(N, M \le 2\times 10^5\) なので、Pythonでは sys.stdin.buffer.read() などの高速入力が安全です。

• \(L_j, R_j\) は入力が1-indexedなので、実装では -1 して0-indexedに揃えると扱いやすいです。

• 成長量の合計や目標値 \(T_i\) は最大で \(10^{18}\) 級になり得ますが、Pythonの int は任意精度なのでそのまま計算できます（他言語なら int64 が必要）。

• 差分配列の右端処理で R+1 < N の条件を忘れると範囲外アクセスになるため注意します（提示コードはここを正しく分岐しています）。

  ソースコード

import sys

def main():
    it = map(int, sys.stdin.buffer.read().split())
    N = next(it)
    M = next(it)

    H = [next(it) for _ in range(N)]
    T = [next(it) for _ in range(N)]

    diff = [0] * (N + 1)  # diff[N] is sentinel
    for _ in range(M):
        L = next(it) - 1
        R = next(it) - 1
        W = next(it)
        diff[L] += W
        if R + 1 < N:
            diff[R + 1] -= W

    cur = 0
    ans = 0
    for i in range(N):
        cur += diff[i]
        if H[i] + cur >= T[i]:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。