Overview

Given \(N\) products, apply \(Q\) “range addition (discount)” operations, and count the number of products whose final price becomes 0 yen or less (i.e., the total discount amount is greater than or equal to the initial price).

Analysis

Naive Approach

For each coupon, we could update the prices of products one by one from \(L_j\) to \(R_j\). However, this method requires up to \(N\) operations per coupon, resulting in a worst-case time complexity of \(O(N \times Q)\). Since \(N, Q \leq 2 \times 10^5\) in this problem, this would require up to approximately \(4 \times 10^{10}\) operations, which will not fit within the time limit.

Efficient Approach

What this problem asks for is “the final state after all coupons have been applied.” Since we don’t need to check intermediate prices, a technique for efficiently performing range additions is effective. For each product \(i\), we only need to determine “whether the final total discount amount is at least \(W_i\),” so we use the imos method (difference array) to compute the total discount amounts.

Algorithm

Imos Method (Difference Array)

The operation of adding a value \(D\) to a range \([L, R]\) can be sped up using a difference array diff.

1. Initialize an array diff of length \(N+2\) with zeros.
2. For each coupon \((L_j, R_j, D_j)\), update only the following 2 positions:
   • diff[L_j] += D_j
   • diff[R_j + 1] -= D_j
3. After processing all coupons, compute the prefix sum of diff from left to right.
   • The total discount amount for the \(i\)-th product is \(\sum_{k=1}^{i} diff[k]\).
4. For each product \(i\), if total discount amount >= W_i, then the final price of that product is 0 yen.

Using this technique, each coupon can be processed in \(O(1)\), and the final aggregation takes \(O(N)\).

Complexity

• Time Complexity: \(O(N + Q)\)
  • Processing coupons takes \(O(Q)\), and computing the prefix sum and checking conditions takes \(O(N)\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used for the array holding product prices and the difference array (for the imos method).

Implementation Notes

• Fast I/O: Since \(N\) and \(Q\) can be large, in Python, reading all input at once using sys.stdin.read().split() can reduce execution time.

• Index Handling: The problem uses 1-indexed notation (product numbers 1 through N), but arrays are often 0-indexed. Since we access R_j + 1 when updating the difference array, allocating a slightly larger array size (such as \(N+2\)) prevents out-of-bounds errors.

• Magnitude of Values: Total discount amounts and initial prices can exceed \(10^9\), but Python natively supports arbitrary-precision integers, so overflow is not a concern.

  Source Code

import sys

def solve():
    # 入力を一括で読み込み、スペース区切りで分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 商品の個数 N と クーポンの枚数 Q
    N = int(input_data[0])
    Q = int(input_data[1])
    
    # 各商品の初期価格 W_i (1-indexedを0-indexedとして扱う)
    W = [int(x) for x in input_data[2:2+N]]
    
    # いもす法（差分配列）を用いて各商品に適用される合計割引額を計算します
    # 商品番号は 1 から N なので、サイズ N + 2 の配列を用意します
    diff = [0] * (N + 2)
    
    # クーポンの情報を処理します
    # 各クーポンは L_j から R_j の範囲に D_j の割引を適用します
    idx = 2 + N
    for _ in range(Q):
        l = int(input_data[idx])
        r = int(input_data[idx+1])
        d = int(input_data[idx+2])
        diff[l] += d
        diff[r + 1] -= d
        idx += 3
        
    # 差分配列を累積和することで、各商品の最終的な合計割引額を求めます
    ans = 0
    current_discount = 0
    for i in range(1, N + 1):
        current_discount += diff[i]
        # 商品 i の初期価格は W[i-1]
        # 合計割引額が初期価格以上であれば、最終的な価格は 0 円になります
        if current_discount >= W[i-1]:
            ans += 1
            
    # 結果を出力します
    print(ans)

if __name__ == "__main__":
    solve()

---

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