Overview

We need to find the total sum of coins collected through multiple range collections (intervals). Since coins cannot be collected more than once, we essentially need to calculate the “total coins in treasure chests contained in the union of all magic intervals.”

Analysis

Key Insight

• A treasure chest’s coins are collected if it falls within the range of any magic spell even once, and it cannot be collected again after that.
• This means for each treasure chest, all that matters is “whether it is contained in at least one interval \([L_j, R_j]\).”
• Therefore, the problem can be rephrased as: gather the treasure chests (points) contained in the union of \(M\) intervals, and sum up their coins.

Why the Naive Approach Fails

• If we “search for and add all treasure chests within the interval” for each magic spell, the worst case is \(M \times N = 4 \times 10^{10}\), which will certainly result in TLE.
• Additionally, when intervals overlap, the same treasure chest would be counted multiple times, requiring duplicate elimination.

Solution Strategy

1. First, sort the intervals and merge overlapping ones to create a list of disjoint intervals (the union).
2. Sort the treasure chests by coordinate as well, then scan the merged intervals from left to right, using two pointers to add each relevant treasure chest exactly once.

(Example) - If the intervals are \([1,5], [3,7], [10,12]\), the union is \([1,7], [10,12]\). - We only need to count treasure chests falling within these 2 intervals, and no duplicate counting occurs.

Algorithm

1. Sort the treasure chests \((X_i, C_i)\) in ascending order by coordinate \(X_i\).
2. Sort the intervals \((L_j, R_j)\) in ascending order by \(L_j\).
3. Scan the sorted intervals from left to right, merging overlapping (or adjacent) intervals to create merged.
   • Maintain the current interval as \((cur\_l, cur\_r)\)
   • If the next interval \((l, r)\) satisfies \(l \le cur\_r + 1\), they can be connected, so set \(cur\_r = \max(cur\_r, r)\)
   • Otherwise, finalize the current interval by adding it to merged, and start a new interval
4. For each interval \([l, r]\) in merged, advance through the treasure chest array using pointer i:
   • Treasure chests with \(X_i < l\) do not fall in this interval, so skip past them
   • While \(l \le X_i \le r\), add the coins and advance
   • Since treasure chests are in ascending order, once i advances it never goes back, so all treasure chests are processed at most once

This approach naturally eliminates “double collection due to overlapping intervals” through interval merging.

Complexity

• Time complexity: \(O(N \log N + M \log M)\) (dominated by sorting the treasure chests and intervals; the scanning itself is \(O(N+M)\))
• Space complexity: \(O(N + M)\) (for storing input and merge results)

Implementation Notes

• In the interval merging step, we merge not only overlapping intervals but also “adjacent” ones (condition \(l \le cur\_r + 1\)). Since treasure chests have integer coordinates in this problem, merging adjacent intervals does not change the answer and keeps the implementation concise.

• When processing merged from left to right, using pointer i on the treasure chest side to advance in one direction allows fast aggregation without duplicates.

• The number of coins or the total sum can be as large as \(N \times 10^9\), so while this is not an issue in Python, other languages require \(64\)-bit integers (long long).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)

    chests = []
    for _ in range(N):
        x = next(it)
        c = next(it)
        chests.append((x, c))

    intervals = []
    for _ in range(M):
        l = next(it)
        r = next(it)
        intervals.append((l, r))

    chests.sort()
    intervals.sort()

    merged = []
    if intervals:
        cur_l, cur_r = intervals[0]
        for l, r in intervals[1:]:
            if l <= cur_r + 1:
                if r > cur_r:
                    cur_r = r
            else:
                merged.append((cur_l, cur_r))
                cur_l, cur_r = l, r
        merged.append((cur_l, cur_r))

    ans = 0
    i = 0
    for l, r in merged:
        while i < N and chests[i][0] < l:
            i += 1
        while i < N and chests[i][0] <= r:
            ans += chests[i][1]
            i += 1

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.