Overview

This problem requires performing \(Q\) range addition operations on \(N\) customers and counting the number of customers whose final points meet or exceed a threshold. We use a difference array (also known as the “imos method”) to efficiently handle the range additions.

Analysis

Naive Approach and Its Issues

A straightforward approach would be to iterate through each campaign \(j\) and increment the points for all customers in the range \([L_j, R_j]\) one by one.

for j in range(Q):
    for i in range(L[j], R[j] + 1):
        A[i] += X[j]

However, this method requires updating up to \(N\) customers per campaign, resulting in an overall time complexity of \(O(NQ)\). Since \(N, Q \leq 2 \times 10^5\), this could require up to \(4 \times 10^{10}\) operations in the worst case, leading to TLE (Time Limit Exceeded).

Key Insight

The order of campaigns does not affect the final result. We only need to know the total additional points each customer receives in the end.

For example, suppose customer 3 is targeted by the following campaigns: - Campaign 1: +5 - Campaign 3: +3

In this case, customer 3’s additional points are \(5 + 3 = 8\).

Algorithm

We use a difference array (imos method). This technique records range additions in \(O(1)\) and reconstructs the value at each position in \(O(N)\) at the end.

How the Difference Array Works

1. Prepare a difference array diff: Record the operation of adding \(X\) to range \([L, R]\) as follows:

   • diff[L] += X (add \(+X\) at the start of the range)
   • diff[R+1] -= X (add \(-X\) at the position after the end of the range)

2. Reconstruct using prefix sum: Taking the prefix sum of diff gives the added value at each position

Concrete Example

For \(N = 5\), adding \(+10\) to range \([2, 4]\):

diff = [0, 0, 0, 0, 0, 0, 0]  # indices 0 to 6
           ↓
diff = [0, 0, 10, 0, 0, -10, 0]  # diff[2] += 10, diff[5] -= 10

Taking prefix sum:
add = [0, 0, 10, 10, 10, 0, ...]
          ↑   ↑   ↑
       +10 is added to customers 2, 3, 4

Overall Flow

1. Record all campaigns in the difference array: \(O(Q)\)
2. Take prefix sum to calculate the added value for each customer: \(O(N)\)
3. For each customer, check if “initial points + added value ≥ threshold” and count: \(O(N)\)

Complexity

• Time complexity: \(O(N + Q)\)
  • Reading customer information: \(O(N)\)
  • Recording campaigns: \(O(Q)\)
  • Prefix sum calculation and checking: \(O(N)\)
• Space complexity: \(O(N)\)
  • Arrays A, T, diff, add are each \(O(N)\)

Implementation Notes

• The difference array size must be at least \(N + 2\) (since we access diff[R+1], and when \(R = N\), we access diff[N+1])
• Using 1-indexed implementation makes it easier to match the problem statement
• Point values are on the order of \(10^9\), and with up to \(Q\) additions, the total can reach approximately \(2 \times 10^{14}\). Python handles integer overflow automatically, but other languages require 64-bit integer types

Source Code

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    
    A = [0] * (N + 1)
    T = [0] * (N + 1)
    
    for i in range(1, N + 1):
        a, t = map(int, input().split())
        A[i] = a
        T[i] = t
    
    # Use difference array to efficiently handle range additions
    diff = [0] * (N + 2)
    
    for _ in range(Q):
        L, R, X = map(int, input().split())
        diff[L] += X
        diff[R + 1] -= X
    
    # Take prefix sum to get the added value for each customer
    add = [0] * (N + 1)
    current = 0
    for i in range(1, N + 1):
        current += diff[i]
        add[i] = current
    
    # Count the number of customers who decided to participate
    count = 0
    for i in range(1, N + 1):
        if A[i] + add[i] >= T[i]:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.