Overview

This problem asks you to apply all range additions (campaigns) to determine each customer’s travel points, then count how many customers end up with points greater than or equal to their threshold \(T_i\).

Analysis

Each campaign is an operation that “adds \(X_j\) to everyone in the range \([L_j, R_j]\).”
If we implement this naively by adding to every person in the range each time, the worst case would be:

• \(O(N)\) updates per campaign
• \(Q\) campaigns total

resulting in \(O(NQ)\) total operations (up to around \(4\times 10^{10}\)), which would cause a Time Limit Exceeded (TLE).

The key observation here is as follows:

• We only need to know “how much total was added to each position (each customer)” as the result of all range additions.
• Range additions can be recorded in \(O(1)\) using a difference array (imos method), and then restored all at once at the end using prefix sums.

Intuition for the Difference Array (Small Example)

For example, suppose \(N=5\) and we want to add \(+3\) to the range \([2,4]\).
We prepare a difference array diff and write:

• diff[2] += 3 (the increase starts from position 2)
• diff[5] -= 3 (revert back starting from position 5, which is one past position 4)

Then, by taking the prefix sum of diff, we can recover the state where only positions 2 through 4 have been increased by +3.

By applying this idea to all campaigns, we can efficiently compute the total additions.

Algorithm

1. Read the initial value \(A_i\) and threshold \(T_i\) for each customer.
2. Prepare a difference array diff of length \(N+2\) (with extra room to handle index boundaries).
3. For each campaign \((L, R, X)\), do the following:
   • diff[L] += X
   • diff[R+1] -= X
4. Update the prefix sum add from left to right:
   • add += diff[i] gives “the total addition that customer \(i\) ultimately receives”
5. For each customer, if \(A_i + add \ge T_i\), count them as confirmed participants.
6. Output the count.

In this method, instead of directly applying range updates to the array, we only record where “the increase starts” and where “the increase ends,” then restore everything all at once at the end.

Complexity

• Time complexity: \(O(N+Q)\)
  (Each campaign is recorded in \(O(1)\), and the final prefix sum computation and evaluation take \(O(N)\))
• Space complexity: \(O(N)\)
  (For storing the difference array and input arrays)

Implementation Notes

• Since the input \(L, R\) are 1-indexed, it is convenient to design the difference array to primarily use diff[1..N] (the code follows this form).

• Since we access diff[R+1], we set the array length to N+2 to avoid out-of-bounds access.

• In the final evaluation, the customer arrays A, T are 0-indexed while the prefix sum is 1-indexed, causing an offset, so we align them using A[i-1], T[i-1].

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    N = int(next(it))
    Q = int(next(it))

    A = [0] * N
    T = [0] * N
    for i in range(N):
        A[i] = int(next(it))
        T[i] = int(next(it))

    diff = [0] * (N + 2)
    for _ in range(Q):
        L = int(next(it))
        R = int(next(it))
        X = int(next(it))
        diff[L] += X
        diff[R + 1] -= X

    ans = 0
    add = 0
    for i in range(1, N + 1):
        add += diff[i]
        if A[i - 1] + add >= T[i - 1]:
            ans += 1

    sys.stdout.write(str(ans))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.