Overview

This problem requires determining how many customers reach their threshold after multiple “range addition (campaign)” operations are applied to customers who each have an “initial points” value and a “target threshold.”

Analysis

Naive Approach

The first idea that comes to mind is to loop through customers from \(L_j\) to \(R_j\) for each campaign and add points one by one. However, both the number of customers \(N\) and the number of campaigns \(Q\) can be up to \(2 \times 10^5\). In the worst case (e.g., all campaigns target the entire range), the time complexity becomes \(O(N \times Q)\), requiring approximately \(4 \times 10^{10}\) operations. This far exceeds the typical time limit (around 2 seconds), resulting in TLE (Time Limit Exceeded).

Efficient Solution

The key insight of this problem is that “we only need to know the final points after all campaigns have been applied.” The operation of adding a value to an entire range at once and then retrieving the result at the end can be drastically sped up using the “imos method (difference array technique).”

Additionally, organizing the condition for judgment, customer \(i\) satisfies the condition if and only if: $\((\text{initial points } A_i) + (\text{total added points } S_i) \geq (\text{threshold } T_i)\)\( Rearranging this: \)\(S_i \geq T_i - A_i\)\( By precomputing "how many more points are needed (\)T_i - A_i$)” for each customer, we only need to compare it with the total added points at the end.

Algorithm

Imos Method (Difference Array) Procedure

1. Initialize an array diff of length \(N+2\) with \(0\).
2. For each campaign \((L_j, R_j, X_j)\), perform the following operations:
   • Add \(X_j\) to diff[L_j]
   • Subtract \(X_j\) from diff[R_j + 1] Each of these operations takes \(O(1)\) per campaign.
3. After all campaigns are processed, compute the prefix sum of diff from the beginning.
   • \(S_i = \sum_{k=1}^{i} \text{diff}[k]\) This \(S_i\) represents the total points added to customer \(i\).
4. For each customer, check whether \(S_i \geq T_i - A_i\), and count the number of customers satisfying the condition.

Complexity

• Time Complexity: \(O(N + Q)\)
  • Computing the required points for each customer: \(O(N)\)
  • Difference array updates for campaigns: \(O(Q)\)
  • Prefix sum computation and final judgment: \(O(N)\)
  • Since \(N, Q \leq 2 \times 10^5\), this comfortably fits within the time limit.
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store customer data and the difference array.

Implementation Notes

• Fast I/O: When handling input on the order of \(10^5\) in Python, repeatedly calling input() is slow, so it is standard practice to read all input at once using sys.stdin.read().split() or similar methods.

• Index Handling: The problem uses \(1\)-indexed customer numbers starting from \(1\). To prevent out-of-bounds array access, it is necessary to set the size of the difference array to \(N+2\) or similar.

• Negative Required Points: If a customer already exceeds the threshold in the initial state (\(T_i - A_i \leq 0\)), the condition is always satisfied as long as the added points are non-negative. In this solution, the computation handles this case correctly as-is.

  Source Code

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()

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