Overview

We efficiently compute the “total discount amount” for each product and count the number of products whose price drops to \(W_i\) or below (i.e., the total discount amount is at least \(W_i\)).

Analysis

Coupon \(j\) applies a discount of \(D_j\) yen to all products in the interval \([L_j, R_j]\). After applying all coupons, the final price of product \(i\) is: [ \max(0,\; W_i - (\text{total discount applied to product }i)) ]

Therefore, the condition for the price to become \(0\) yen is: [ \text{total discount} \ge W_i ] The key insight is that we don’t need to simulate the actual final price — we only need to know the total discount applied to each product.

Why the naive approach fails

If we update the entire interval \([L_j, R_j]\) for each coupon, in the worst case: - Number of coupons \(Q = 2 \times 10^5\) - Maximum interval length \(N = 2 \times 10^5\)

This results in \(O(NQ)\) updates (approximately \(4 \times 10^{10}\)), which is far too slow (TLE).

Solution

The operation “add a uniform value to an interval” can be efficiently handled using a difference array (imos method). By converting each interval addition into updates at only the endpoints, and then taking the prefix sum at the end, we can obtain the total discount for each element in \(O(N+Q)\).

Algorithm

Prepare a difference array diff (of length \(N\)), and process each coupon \((L, R, D)\) as follows (using 0-indexing):

1. diff[L] += D
2. diff[R+1] -= D (only when \(R+1 < N\))

With this setup, when we compute the prefix sum cur of diff from left to right: - cur represents the total discount amount at that position.

Finally, for each product \(i\): - If cur >= W[i], the final price is \(0\) yen.

So we count the number of products satisfying this condition and output the result.

Concrete Example

If \(N=5\) and there is a coupon applying \(+3\) to \([2,4]\) (1-indexed), which is \([1,3]\) in 0-indexed: - diff[1] += 3 - diff[4] -= 3

The prefix sum then adds +3 only to positions 1 through 3. Multiple coupons can be superimposed in the same way.

Complexity

• Time complexity: \(O(N+Q)\) (coupon processing is \(O(Q)\), prefix sum and checking is \(O(N)\))
• Space complexity: \(O(N)\) (for the difference array, etc.)

Implementation Notes

• Since the input scale is up to \(2 \times 10^5\), using sys.stdin.buffer.read() for bulk reading is faster.

• \(L, R\) are 1-indexed in the input, so in the code we subtract \(1\) to convert to 0-indexed.

• The update at diff[R+1] is only performed when R+1 < N to avoid out-of-bounds access.

• The condition that the price cannot go below \(0\) is handled simply by checking cur >= W[i] (there is no need to compute the actual final price).

  Source Code

import sys

def main():
    it = map(int, sys.stdin.buffer.read().split())
    N = next(it)
    Q = next(it)
    W = [next(it) for _ in range(N)]

    diff = [0] * (N + 1)
    for _ in range(Q):
        L = next(it) - 1
        R = next(it) - 1
        D = next(it)
        diff[L] += D
        if R + 1 < N:
            diff[R + 1] -= D

    ans = 0
    cur = 0
    for i in range(N):
        cur += diff[i]
        if cur >= W[i]:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.