Overview

There are \(N\) products, each of which has discounts applied by multiple interval coupons. We need to find the number of products whose final price becomes \(0\) yen.

Analysis

Each coupon applies a discount of \(D_j\) yen to all products in a certain interval \([L_j, R_j]\).
A naive approach that directly adds the discount amount to every product in the interval for each coupon would take \(O(Q \times N)\) in the worst case, which results in TLE given the large constraints.

The key observation is that “uniform addition over an interval” is performed frequently. Such operations can be handled efficiently using the imos method (prefix sum technique) or difference array technique.
Specifically, the operation of adding \(D\) to the interval \([L, R]\) can be represented using a difference array diff as follows:

• diff[L] += D
• diff[R+1] -= D

After performing all such operations, taking the prefix sum of diff gives us the total discount amount applied to each element.

The final price is \(\max(0, W_i - \text{discount}_i)\), and this becomes \(0\) when \(W_i \leq \text{discount}_i\). The answer is simply the count of products satisfying this condition.

Algorithm

1. Prepare a difference array diff of size \(N+1\).
2. For each coupon \((L, R, D)\):
   • diff[L] += D
   • diff[R+1] -= D
3. Compute the prefix sum of diff to obtain the total discount applied to each product.
4. For each product \(i\), increment the count if \(W_i \leq \text{discount}_i\).
5. Output the count.

Complexity

• Time complexity: \(O(N + Q)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Since coupon intervals are given in 1-indexed format, they need to be converted to 0-indexed for internal processing.

• By setting the size of the difference array to \(N+1\), we prevent out-of-bounds access when using R+1.

• To ensure the final price does not become negative, the comparison should check the condition where \(\max(0, W_i - \text{discount}_i) = 0\).

  Source Code

import sys
from itertools import accumulate

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    Q = int(data[idx])
    idx += 1
    
    W = [int(data[idx + i]) for i in range(N)]
    idx += N
    
    # クーポン情報を読み取る
    coupons = []
    for _ in range(Q):
        L = int(data[idx]) - 1  # 0-indexed
        idx += 1
        R = int(data[idx]) - 1
        idx += 1
        D = int(data[idx])
        idx += 1
        coupons.append((L, R, D))
    
    # 遅延評価セグメント木を用いて効率的に処理する
    # 各要素は価格から引かれる合計ディスカウント
    # 最終的な価格 = max(0, W[i] - total_discount[i])
    # したがって、total_discount[i] >= W[i] なら価格は0になる
    
    # 区間加算と区間取得ができるデータ構造が必要
    # ここでは、差分更新＋累積和で対応する
    
    # 差分配列を用意して区間[L,R]にDを足す操作を行う
    diff = [0] * (N + 1)
    for L, R, D in coupons:
        diff[L] += D
        if R + 1 < N:
            diff[R + 1] -= D
    
    # 累積和で各商品にかかる合計ディスカウントを計算
    discounts = list(accumulate(diff[:-1]))
    
    count = 0
    for i in range(N):
        if W[i] <= discounts[i]:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.