Overview

This problem asks you to apply \(Q\) coupons (range discounts) to \(N\) products and count how many products end up with a price of \(0\) yen. We use a difference array to efficiently handle range additions.

Analysis

Problems with the Naive Approach

Consider the naive method where for each coupon, we add the discount amount \(D_j\) to all products in the target range \([L_j, R_j]\).

for each coupon (L, R, D):
    for i = L to R:
        discount[i] += D

In this case, a single coupon may update up to \(N\) products, resulting in an overall time complexity of \(O(NQ)\). When \(N, Q \leq 2 \times 10^5\), this requires up to \(4 \times 10^{10}\) operations in the worst case, causing TLE (Time Limit Exceeded).

Key to the Solution: Efficient Range Addition

To speed up the operation “add value \(D\) to all elements in range \([L, R]\)”, we use a difference array (imos method).

The idea behind the difference array is as follows: - diff[L] += D: The discount starts at position \(L\) - diff[R+1] -= D: The discount ends at position \(R+1\)

By taking the prefix sum of the difference array at the end, we obtain the total discount amount at each position.

Concrete Example

For \(N = 5\) and coupon \((L=2, R=4, D=10)\):

Difference array: [0, 0, +10, 0, 0, -10, 0]
                       ↑L         ↑R+1
Prefix sum:       [0, 0,  10, 10, 10,  0, 0]
                     Products 2,3,4 get 10 yen discount

Algorithm

1. Read input: Read the number of products \(N\), number of coupons \(Q\), and the price \(W_i\) of each product

2. Build the difference array:

   • Prepare a difference array diff of length \(N+2\) (initialized to \(0\))
   • For each coupon \((L_j, R_j, D_j)\):
     • diff[L_j] += D_j
     • diff[R_j + 1] -= D_j

3. Calculate discount amounts using prefix sum:

   • Compute the prefix sum of the difference array to calculate the total discount for each product \(i\)
   • If the discount amount \(\geq\) original price \(W_i\), that product becomes \(0\) yen

4. Count: Output the number of products whose price became \(0\) yen

Complexity

• Time Complexity: \(O(N + Q)\)

  • Adding to the difference array: \(O(1)\) per coupon, so \(O(Q)\) total
  • Computing prefix sum and checking: \(O(N)\)

• Space Complexity: \(O(N)\)

  • Product price array: \(O(N)\)
  • Difference array: \(O(N)\)

Implementation Notes

1. Be careful with 1-indexed: Product numbers range from \(1\) to \(N\), so pay attention to array indices. The difference array accesses diff[N+1], so allocate length \(N+2\) or more.

2. Be careful with overflow: \(D_j\) can be up to \(10^9\), and there can be up to \(2 \times 10^5\) coupons, so the total discount can reach up to \(2 \times 10^{14}\). Python doesn’t have integer overflow issues, but other languages need to use 64-bit integers.

3. Fast input: Since \(N, Q\) are large, we speed up input by reading everything at once with sys.stdin.read().

Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    W = [0] * (N + 1)
    for i in range(1, N + 1):
        W[i] = int(input_data[idx]); idx += 1
    
    # Use difference array to efficiently handle range addition
    # diff[i] = discount[i] - discount[i-1]
    diff = [0] * (N + 2)
    
    for _ in range(Q):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        D = int(input_data[idx]); idx += 1
        diff[L] += D
        diff[R + 1] -= D
    
    # Calculate discount for each product using prefix sum
    discount = 0
    count = 0
    for i in range(1, N + 1):
        discount += diff[i]
        if discount >= W[i]:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.