概要

この問題は、各顧客に設定された「初期ポイント」と「目標の閾値」に対し、複数回の「区間加算（キャンペーン）」を行った結果、最終的に何人が閾値に到達するかを求める問題です。

考察

素朴なアプローチ

まず思いつくのは、各キャンペーンごとに \(L_j\) から \(R_j\) までの顧客をループで回し、ポイントを加算していく方法です。 しかし、顧客数 \(N\) とキャンペーン数 \(Q\) はともに最大 \(2 \times 10^5\) です。最悪の場合（すべてのキャンペーンが全区間対象の場合など）、計算量は \(O(N \times Q)\) となり、約 \(4 \times 10^{10}\) 回の計算が必要になります。これは一般的な制限時間（2秒程度）を大幅に超えてしまい、TLE（実行時間制限超過）となります。

効率的な解決策

この問題のポイントは、「すべてのキャンペーンが終わった後の最終的なポイントだけが分かればよい」という点です。 特定の区間に一括で値を加算し、最後にその結果を取得する操作は、「いもす法（差分更新）」を用いることで劇的に高速化できます。

また、判定条件を整理すると、顧客 \(i\) が参加する条件は以下の通りです。 $\((\text{初期ポイント } A_i) + (\text{加算された合計ポイント } S_i) \geq (\text{閾値 } T_i)\)\( これを変形すると： \)\(S_i \geq T_i - A_i\)\( となります。あらかじめ各顧客について「あと何ポイント必要か（\)T_i - A_i$）」を計算しておけば、最後に加算合計と比較するだけで済みます。

アルゴリズム

いもす法（差分更新）の手順

1. 長さ \(N+2\) の配列 diff を \(0\) で初期化します。
2. 各キャンペーン \((L_j, R_j, X_j)\) について、以下の操作を行います。
   • diff[L_j] に \(X_j\) を加える
   • diff[R_j + 1] から \(X_j\) を引く この操作は各キャンペーンにつき \(O(1)\) で終わります。
3. すべてのキャンペーンが終わった後、diff の前から順番に累積和をとります。
   • \(S_i = \sum_{k=1}^{i} \text{diff}[k]\) この \(S_i\) が、顧客 \(i\) に加算された最終的なポイントの合計になります。
4. 各顧客について \(S_i \geq T_i - A_i\) を判定し、条件を満たす人数をカウントします。

計算量

• 時間計算量: \(O(N + Q)\)
  • 各顧客の必要ポイント計算に \(O(N)\)
  • キャンペーンの差分更新に \(O(Q)\)
  • 累積和の計算と最終判定に \(O(N)\)
  • \(N, Q \leq 2 \times 10^5\) なので、制限時間内に十分間に合います。
• 空間計算量: \(O(N)\)
  • 顧客データや差分更新用の配列を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Pythonで \(10^5\) オーダーの入力を扱う場合、input() を繰り返すと遅いため、sys.stdin.read().split() などで一括で読み込むのが定石です。

• インデックスの扱い: 問題文は顧客番号が \(1\) から始まる \(1\)-indexed です。配列の範囲外参照を防ぐため、差分更新用の配列サイズを \(N+2\) にするなどの工夫が必要です。

• 負の必要ポイント: 初期状態で既に閾値を超えている場合（\(T_i - A_i \leq 0\)）、加算ポイントが \(0\) 以上であれば必ず条件を満たします。今回の解法では、そのまま計算しても正しく判定されます。

  ソースコード

import sys

def solve():
    # 全ての入力を一度に読み込み、整数のリストに変換します。
    # これはPythonにおいて大量の入力を高速に処理する標準的な手法です。
    try:
        data = list(map(int, sys.stdin.read().split()))
    except EOFError:
        return
    
    if not data:
        return
    
    # 顧客の数 N とキャンペーンの回数 Q を取得します。
    N = data[0]
    Q = data[1]
    
    # 各顧客が旅行に参加するために追加で必要なポイントを計算します。
    # diff_needed[i] = (閾値 T_i) - (初期ポイント A_i)
    # 既に閾値を超えている場合は 0 以下の値になります。
    diff_needed = [0] * N
    for i in range(N):
        # 顧客 i の情報は data[2 + 2*i] (A_i) と data[2 + 2*i + 1] (T_i) にあります。
        A_i = data[2 + 2*i]
        T_i = data[2 + 2*i + 1]
        diff_needed[i] = T_i - A_i
        
    # いもす法（Difference Array）を用いて、各顧客に加算される合計ポイントを計算します。
    # キャンペーンは [L_j, R_j] の範囲に X_j を加えるため、
    # 差分配列の L_j に +X_j、R_j + 1 に -X_j を記録します。
    # 顧客番号は 1-indexed なので、配列サイズは N + 2 とします。
    points_added_diff = [0] * (N + 2)
    offset = 2 + 2 * N
    for j in range(Q):
        # j 番目のキャンペーンの情報は data[offset + 3*j] から始まります。
        L_j = data[offset + 3*j]
        R_j = data[offset + 3*j + 1]
        X_j = data[offset + 3*j + 2]
        points_added_diff[L_j] += X_j
        points_added_diff[R_j + 1] -= X_j
        
    ans = 0
    current_total_X = 0
    # 差分配列の累積和をとることで、各顧客 i に加算された最終的なポイントを求めます。
    for i in range(1, N + 1):
        current_total_X += points_added_diff[i]
        
        # 「初期ポイント + 加算ポイント >= 閾値」
        # すなわち「加算ポイント >= 閾値 - 初期ポイント」であれば参加決定です。
        if current_total_X >= diff_needed[i-1]:
            ans += 1
            
    # 結果を出力します。
    sys.stdout.write(str(ans) + '\n')

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。