Overview

A problem where you process range addition queries and then determine whether each element meets or exceeds a threshold.

Analysis

In this problem, there are up to \(2 \times 10^5\) customers and the same number of campaigns. If we naively perform range addition for each query, the worst-case complexity becomes \(O(NQ) = O(4 \times 10^{10})\), which clearly exceeds the time limit.

To efficiently handle “uniform addition over a range,” we use a technique called the imos method (difference array technique). This method uses a difference array to process range additions in constant time, and then computes the prefix sum at the end to obtain the actual values.

The final points for each customer are the initial value plus the increase from campaigns. We can efficiently compute this increase using the imos method and then perform the final check.

Algorithm

1. Read each customer’s initial points \(A_i\) and threshold \(T_i\).
2. Prepare a difference array diff of size \(N+1\) to record the point increases from campaigns.
3. For each campaign \([L_j, R_j]\), perform diff[L_j] += X_j and diff[R_j + 1] -= X_j (converting from 1-indexed to 0-indexed).
4. Compute the prefix sum of diff to obtain the point increase final_add[i] for each customer.
5. For each customer, if the final points \(A_i + \text{final\_add}[i]\) are at least \(T_i\), increment the count.
6. Output the final count.

Example

For instance, let \(N=3\), initial points \(A = [10, 20, 30]\), and thresholds \(T = [25, 30, 40]\).

Campaigns: - Add \(5\) to range \([1, 2]\) → customers 1 and 2 get \(+5\) - Add \(10\) to range \([2, 3]\) → customers 2 and 3 get \(+10\)

Difference array operations: - diff[0] += 5, diff[2] -= 5 - diff[1] += 10, diff[3] -= 10

After computing the prefix sum: - final_add = [5, 15, 10]

Final points: - Customer 1: \(10 + 5 = 15 < 25\) → NG - Customer 2: \(20 + 15 = 35 \geq 30\) → OK - Customer 3: \(30 + 10 = 40 \geq 40\) → OK

Answer: 2 people

Complexity

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

Implementation Notes

• Convert indices from 1-indexed to 0-indexed (use \(L-1\) and \(R-1\)).
• Set the size of the difference array to \(N+1\) to prevent out-of-bounds access.
• When computing the final prefix sum, extract only the first \(N\) elements (excluding the extra element at the end).

## Source Code

```python
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
    
    A = [0] * N
    T = [0] * N
    for i in range(N):
        A[i] = int(data[idx])
        idx += 1
        T[i] = int(data[idx])
        idx += 1
    
    # 差分更新用の配列
    diff = [0] * (N + 1)
    
    for _ in range(Q):
        L = int(data[idx]) - 1  # 0-indexed
        idx += 1
        R = int(data[idx]) - 1
        idx += 1
        X = int(data[idx])
        idx += 1
        
        diff[L] += X
        diff[R + 1] -= X
    
    # 累積和で各顧客の最終ポイント増分を計算
    final_add = list(accumulate(diff))[:N]
    
    count = 0
    for i in range(N):
        final_point = A[i] + final_add[i]
        if final_point >= T[i]:
            count += 1
    
    print(count)

if __name__ == "__main__":
    main()

---

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