Overview

This is a problem where you collect coins from treasure chests lined up in a straight line by casting magic over multiple intervals. Since you cannot collect from the same treasure chest twice, what matters for each treasure chest is only “whether it was covered at least once or not.”

Analysis

Key Insight

Since coins cannot be collected again from a treasure chest that has already been collected from, even if multiple magic ranges overlap, the coins from that treasure chest are counted only once.

In other words, we need to find the total coins of treasure chests contained in the union of \(M\) intervals \([L_1, R_1], [L_2, R_2], \ldots, [L_M, R_M]\).

Problem with the Naive Approach

If we check each treasure chest one by one for each magic spell and manage whether it has been “already collected,” the worst-case time complexity becomes \(O(NM)\). When both \(N\) and \(M\) are \(2 \times 10^5\), this requires \(4 \times 10^{10}\) operations, resulting in TLE.

Solution

To efficiently compute the union of intervals, we perform interval merging. By sorting all query intervals and merging overlapping parts, we can count treasure chests without duplication.

For example, intervals \([2, 5]\) and \([4, 8]\) overlap, so they are merged into \([2, 8]\). Intervals \([2, 5]\) and \([7, 8]\) do not overlap, so they remain separate.

Algorithm

1. Sort the treasure chests by coordinate and build a prefix sum array of coins.
2. Sort the query intervals and merge overlapping intervals.
   • Sort by left endpoint. If the next interval’s left endpoint is less than or equal to the current interval’s right endpoint, merge them (update the right endpoint to the larger one).
   • Otherwise, add it as a new interval.
3. For each merged interval \([l, r]\), use binary search to find the index range of treasure chests satisfying \(l \leq X_i \leq r\), and retrieve the coin total for that range in \(O(1)\) using the prefix sum.
4. Output the total sum.

Concrete Example

Treasure chests: coordinates \([1, 3, 5, 7, 9]\), coins \([10, 20, 30, 40, 50]\)

Queries: \([2, 5], [4, 8]\) → After merging: \([2, 8]\)

Treasure chests within \([2, 8]\) have coordinates \(3, 5, 7\) → Coins: \(20 + 30 + 40 = 90\)

Complexity

• Time complexity: \(O(N \log N + M \log M)\)
  • \(O(N \log N)\) for sorting treasure chests, \(O(M \log M)\) for sorting queries, and binary searches for each merged interval total \(O(M \log N)\) (the number of merged intervals is at most \(M\)).
• Space complexity: \(O(N + M)\)
  • \(O(N)\) for treasure chest coordinates, coins, and prefix sums; \(O(M)\) for storing queries.

Implementation Notes

• Interval merging: After sorting by left endpoint, compare the left endpoint of adjacent intervals with the current right endpoint to merge them — this is a classic technique. If l <= cr (the new interval’s left endpoint is less than or equal to the current right endpoint), they overlap and should be merged.

• Binary search: Use Python’s bisect_left(sorted_X, l) to get the first index with value \(\geq l\), and bisect_right(sorted_X, r) to get the first index with value \(> r\), then take the difference of prefix sums over that range.

• Prefix sum: To compute the coin total within an interval in \(O(1)\), build a prefix sum array in advance.

  Source Code

import sys
from bisect import bisect_left, bisect_right

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    X = []
    C = []
    for i in range(N):
        x = int(input_data[idx]); idx += 1
        c = int(input_data[idx]); idx += 1
        X.append(x)
        C.append(c)
    
    queries = []
    for j in range(M):
        l = int(input_data[idx]); idx += 1
        r = int(input_data[idx]); idx += 1
        queries.append((l, r))
    
    # Sort treasures by coordinate
    treasures = sorted(zip(X, C), key=lambda t: t[0])
    sorted_X = [t[0] for t in treasures]
    sorted_C = [t[1] for t in treasures]
    
    # We need to find all treasure boxes covered by at least one query interval
    # and sum their coins.
    # 
    # Approach: Use a "interval union" approach with sorting, or use a segment-tree
    # style approach to mark collected boxes.
    #
    # Efficient approach: Merge all query intervals, then for each merged interval,
    # sum coins of treasures in that range.
    
    # Merge intervals
    if M == 0:
        print(0)
        return
    
    queries.sort()
    merged = []
    cl, cr = queries[0]
    for i in range(1, M):
        l, r = queries[i]
        if l <= cr:
            cr = max(cr, r)
        else:
            merged.append((cl, cr))
            cl, cr = l, r
    merged.append((cl, cr))
    
    total = 0
    # prefix sum of sorted_C
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + sorted_C[i]
    
    for l, r in merged:
        # Find indices in sorted_X where l <= X <= r
        left_idx = bisect_left(sorted_X, l)
        right_idx = bisect_right(sorted_X, r)
        total += prefix[right_idx] - prefix[left_idx]
    
    print(total)

main()

---

This editorial was generated by claude4.6opus-thinking.