概要

各花が受ける水の総量を求め、最終乾燥度が閾値 \(T\) 以下かどうかを判定する問題です。鍵は「0でのクランプ（下限制約）が最終結果の判定に影響しない」ことに気づくことです。

考察

素朴なアプローチの問題点

各花に対して \(M\) 回の操作を順に適用するシミュレーションは \(O(NM)\) で、最大 \(10^{11}\) 程度の演算が必要になりTLEします。

重要な気づき：クランプの影響を分析する

花 \(i\) に適用される操作の減少量を順に \(d_1, d_2, \ldots, d_p\) とします。各ステップで値は \(v_k = \max(v_{k-1} - d_k, 0)\) と更新されます。

累積和を \(S_k = d_1 + d_2 + \cdots + d_k\) とすると、最終値は次の公式で表されます：

\[v_p = \max\left(\max(F_i,\ M_p) - S_p,\ 0\right)\]

ここで \(M_p = \max(S_1, S_2, \ldots, S_p)\) は累積和の最大値です。

決定的な簡略化

制約より \(D_j \geq 1\) なので、\(d_k\) はすべて正です。したがって累積和 \(S_1 < S_2 < \cdots < S_p\) は単調増加であり、最大値は常に最後の値 \(M_p = S_p\) となります。

公式に代入すると：

\[v_p = \max(\max(F_i, S_p) - S_p,\ 0) = \max(F_i - S_p,\ 0)\]

つまり、途中で0にクランプされるかどうかに関わらず、最終値は初期値から受けた水の総量を引いて0で切ったものに等しいのです。

判定条件の整理

花 \(i\) が元気な状態 \(\Leftrightarrow\) \(\max(F_i - S_p, 0) \leq T\)

\(T \geq 0\) なので、これは \(F_i - S_p \leq T\)、すなわち：

\[F_i \leq S_p + T\]

と同値です。ここで \(S_p\) は花 \(i\) が受ける水の総量です。

具体例

• 花の初期乾燥度 \(F_i = 10\)、操作で受ける水の総量 \(S_p = 7\)、\(T = 5\) のとき
  • 最終乾燥度: \(\max(10 - 7, 0) = 3 \leq 5\) → 元気 ✓
  • 判定: \(10 \leq 7 + 5 = 12\) → 元気 ✓

アルゴリズム

1. いもす法（差分配列） で各花が受ける水の総量を \(O(N + M)\) で計算する
2. 各花について \(F_i \leq S_i + T\) かどうかを判定し、条件を満たす花の数を数える

差分配列の仕組み： - 配列 diff を用意し、操作 \((L_j, R_j, D_j)\) ごとに diff[L_j-1] += D_j、diff[R_j] -= D_j とする - diff の累積和が各花が受ける水の総量になる

計算量

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

実装のポイント

• \(D_j \geq 1\) という制約が本質的。もし \(D_j = 0\) が許されると累積和が単調増加にならず、この簡略化は使えない

• 差分配列のインデックスの境界に注意（0-indexed と 1-indexed の変換）

• \(F_i\) や \(S_p\) が大きくなりうるため、オーバーフローに注意（Pythonでは問題なし）

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    F = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    
    operations = []
    for j in range(M):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        D = int(input_data[idx]); idx += 1
        operations.append((L, R, D))
    
    # The problem: each operation subtracts D_j from flowers in [L_j, R_j], clamped at 0.
    # Because of the clamping at 0, operations are not simply additive.
    # We need to compute for each flower i: apply operations in order, each time v = max(v - D_j, 0).
    
    # For a single flower with initial value F_i, applying a sequence of subtractions with clamping:
    # v_0 = F_i
    # v_k = max(v_{k-1} - d_k, 0)
    #
    # Let S_k = sum of d_1..d_k that apply to this flower, and M_k = max over all prefixes of partial sums.
    # Actually, let's think differently.
    #
    # After applying subtractions d_1, d_2, ..., d_p (those operations that include flower i, in order):
    # The final value is max(F_i - S, 0) where S accounts for clamping.
    # 
    # Actually: v = max(0, F_i - S_p, min over 1<=k<=p of (F_i - S_k))... no.
    #
    # Known result: if we apply v = max(v - d_k, 0) sequentially, the result is:
    # max(F_i - S_p, 0) where S_p = sum of all d_k, BUT only if F_i never hits 0 in between.
    # If it does hit 0, then effectively the "prefix sums" reset.
    #
    # The exact formula: final value = max(F_i - S_p, -min_{0<=k<=p}(F_i - S_k), 0)
    #   = max(F_i - S_p, S_k_max - F_i ... no
    #
    # Let me re-derive. Let S_0=0, S_k = S_{k-1} + d_k. Then:
    # v_k = max(F_i - S_k, max_{1<=j<=k}(S_j - S_k)... )
    # Actually: v_k = F_i - S_k + max(0, max_{1<=j<=k}(S_j - F_i))
    #         = max(F_i - S_k, max_{1<=j<=k}(S_j) - S_k)
    # Hmm, let me just verify: v_k = max(F_i - S_k, M_k - S_k) where M_k = max(S_1,...,S_k), but also >=0.
    # So v_k = max(F_i - S_k, M_k - S_k, 0) = max(max(F_i, M_k) - S_k, 0).
    #
    # Final: v_p = max(max(F_i, M_p) - S_p, 0) where M_p = max(S_1,...,S_p) and S_p = total sum.
    # Since all d_k >= 1, S_k >= 1 > 0 = S_0, so M_p >= S_1 > 0.
    # If F_i >= M_p: v_p = max(F_i - S_p, 0) = F_i - S_p if F_i >= S_p, else 0.
    # If F_i < M_p: v_p = max(M_p - S_p, 0). Since M_p <= S_p, this is M_p - S_p... wait M_p = max prefix sum <= S_p, so v_p = 0 if M_p=S_p... no M_p could equal S_p. Then v_p=0.
    # Actually M_p <= S_p always (since S_p is itself a prefix sum). So M_p - S_p <= 0, hence v_p = max(F_i - S_p, 0) if F_i >= M_p, else 0... wait that's not right either.
    # v_p = max(max(F_i, M_p) - S_p, 0). If F_i < M_p, then max(F_i,M_p)=M_p, v_p=max(M_p-S_p,0). Since M_p<=S_p, v_p=M_p-S_p if M_p=S_p else 0 when M_p<S_p. So v_p<=0 means v_p=0.
    # So if F_i < M_p: v_p = 0. If F_i >= M_p: v_p = max(F_i - S_p, 0).
    
    # For each flower, we need S_p (sum of D_j for ops covering it) and M_p (max prefix sum of those ops in order).
    # S_p is easy with difference array. M_p is harder since prefix sums depend on order of ops hitting each flower.
    # With N,M up to 2e5, and ops in fixed order, this seems O(NM) worst case naively.
    # But N,M<=2e5, so O(NM)=4e10 is too slow. We need something smarter.
    # However... let me just try the straightforward simulation since maybe with the constraints it passes or we need segment tree with lazy propagation.
    
    # Segment tree with lazy propagation supporting "subtract D clamped at 0" on a range.
    # This is the "chmin/add" segment tree (Chtholly tree or segment tree beats).
    # Actually, "v = max(v - D, 0)" is equivalent to "v = max(v - D, 0)", which is subtract then clamp.
    # This can be handled by a segment tree that tracks values and supports range subtract-and-clamp.
    
    # For N up to 2e5 and M up to 2e5, a simple O(N + M*N/block) sqrt decomposition or just brute force might work if constant is small enough. Let me think about time: 2e5 * 2e5 = 4e10, too slow.
    
    # Let me reconsider the formula approach. Operations are applied in order j=1..M. For flower i, let the subsequence of operations that cover i be j_{i,1} < j_{i,2} < ... < j_{i,p}. The prefix sums are S_k = D_{j_{i,1}} + ... + D_{j_{i,k}}.
    # We showed v_final = max(F_i - S_p, 0) if F_i >= M_p (max of all S_k), else 0.
    # Since S_p >= S_k for... NO. S_p is the total sum which is >= any prefix sum S_k, so M_p <= S_p.
    # If F_i >= M_p = max prefix sum of the applicable operations, then final = max(F_i - S_p, 0).
    # Otherwise final = 0 <= T, so it's "genki".
    
    # So flower i is genki iff: F_i < M_p (then final=0<=T), or F_i >= M_p and F_i - S_p <= T (i.e., F_i <= S_p + T).
    # Equivalently: F_i < M_p, or F_i <= S_p + T.
    # Since M_p <= S_p <= S_p + T, if F_i < M_p then F_i < S_p + T too (when T>=0). So the condition simplifies to F_i <= S_p + T.
    # Wait! That means the clamping doesn't matter for the final check?? Let me verify.
    # If T >= 0: M_p <= S_p <= S_p + T. So F_i < M_p implies F_i <= S_p + T. And F_i >= M_p with F_i <= S_p+T also gives genki. So genki iff F_i <= S_p + T.
    # So we just need S_p = total sum of D_j for operations covering flower i!
    
    # Use difference array for S_p.
    diff = [0] * (N + 1)
    for L, R, D in operations:
        diff[L - 1] += D
        if R < N:
            diff[R] -= D
    
    count = 0
    s = 0
    for i in range(N):
        s += diff[i]
        if F[i] <= s + T:
            count += 1
    
    print(count)

main()

---

この解説は claude4.6opus-thinking によって生成されました。