概要

この問題では、複数回の区間に対する加算操作を高速に処理し、最終的な各要素の値が閾値 \(K\) 以上であるかどうかを判定する必要があります。

考察

まず、素朴な方法として、毎回の水やりについて指定された区間のすべての花壇の水分量を直接更新することを考えます。しかし、最悪の場合、1回の水やりで最大 \(N\) 個の要素を更新し、それが \(M\) 回繰り返されるため、全体の計算量は \(O(NM)\) となり、制約が \(N, M \leq 2 \times 10^5\) なので、現実的ではありません（TLEします）。

そこで、区間に対する一様な加算を効率的に処理するために、「差分更新（いもす法）」というテクニックを使います。これは、区間の始点に加算量を足し、終点の次の位置から減算することで、最後に累積和を取ることで各要素への加算量を求めることができます。

例えば、花壇3から5に水分量10を加える場合、diff[2] += 10, diff[5] -= 10 と設定します。その後、diff の累積和を取ると、各花壇に実際に加算された水分量が求められます。

この方法により、各水やりは定数時間で処理できるため、全体の計算量が \(O(N + M)\) になります。

アルゴリズム

1. 各花壇の初期水分量 \(L_i\) を読み込む。
2. 差分更新用の配列 diff をサイズ \(N+1\) で用意し、0で初期化する。
3. 各水やりに対して、区間 \([X_j, Y_j]\) に \(Z_j\) を加算する操作を以下のように行う：
   • diff[X_j - 1] += Z_j
   • diff[Y_j] -= Z_j
4. diff の累積和を計算し、各花壇に加算された水分量の合計 delta を得る。
5. 各花壇の最終的な水分量を \(L_i + \text{delta}[i]\) で求め、それが \(K\) 以上であればカウントアップする。
6. カウント結果を出力する。

計算量

• 時間計算量: \(O(N + M)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 入力を高速に読み込むために sys.stdin.read を使用している。

• 区間は1-indexedで与えられるため、内部処理では0-indexedに変換する必要がある。

• 差分配列のサイズは \(N+1\) にしておき、終端のインデックス外アクセスを防ぐ。

• 最終的な水分量計算時に delta[i] を加えるのを忘れない。

  ソースコード

import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    
    L = list(map(int, data[3:3+N]))
    
    # 差分更新用の配列
    diff = [0] * (N + 1)
    
    idx = 3 + N
    for _ in range(M):
        X = int(data[idx]) - 1   # 0-indexed
        Y = int(data[idx+1]) - 1
        Z = int(data[idx+2])
        diff[X] += Z
        diff[Y+1] -= Z
        idx += 3
    
    # 差分を累積和して各区間にかかる増加分を計算
    delta = list(accumulate(diff))[:-1]
    
    # 最終的な水分量を計算し、K以上かどうか判定
    count = 0
    for i in range(N):
        final_moisture = L[i] + delta[i]
        if final_moisture >= K:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。