Overview

Given \(N\) treasure chests on a number line, we collect coins through \(M\) range specifications (spells). The problem asks us to find the total number of coins obtained, under the constraint that coins can only be collected from each treasure chest at most once.

Key Observations

There are two major points to consider when solving this problem:

1. How to handle the “collect only once” constraint When multiple spells have overlapping ranges, we must not count treasure chests in the overlapping portions multiple times. To solve this efficiently, we compute the union of the \(M\) given ranges \([L_j, R_j]\). By merging overlapping ranges into one (similar to interval scheduling), we obtain a list of mutually non-overlapping independent ranges.

2. Handling enormous coordinates and queries Since coordinates can be as large as \(10^9\), we cannot directly use coordinates as array indices. Also, since the number of spells \(M\) can be large, checking each treasure chest one by one for each spell would take \(O(N \times M)\) time in the worst case, which would exceed the time limit. By sorting the treasure chests by coordinate and combining prefix sums with binary search, we can efficiently compute the total coins within a specific range.

Algorithm

1. Preparing the treasure chests Sort the treasure chests in ascending order of coordinate \(X_i\). Then compute the prefix sum prefix_sum of the coin counts \(C_i\) in sorted order. This allows us to compute the total coins for any index range \([i, j]\) in \(O(1)\).

2. Merging the ranges Sort the \(M\) ranges \([L_j, R_j]\) in ascending order of the left endpoint \(L_j\). Iterate through them in order: if the current range overlaps with (or is adjacent to) the previous range, extend the range; otherwise, save it as a new independent range.

3. Tallying the coins For each merged range \([L, R]\), perform the following:

   • Use binary search (bisect_left and bisect_right in Python) to find the index of the first treasure chest with coordinate \(\geq L\) and the index of the last treasure chest with coordinate \(\leq R\).
   • Compute the total coins for the identified index range using the prefix sum built in step 1, and add it to the total.

Complexity

• Time complexity: \(O(N \log N + M \log M)\)
  • Sorting treasure chests: \(O(N \log N)\)
  • Sorting and merging spell ranges: \(O(M \log M)\)
  • Binary search for each range: \(O(M \log N)\)
  • Building prefix sums and tallying: \(O(N + M)\)
• Space complexity: \(O(N + M)\)
  • Required to store treasure chest information, prefix sums, and range information.

Implementation Notes

• Fast input: Since \(N\) and \(M\) can be large, using sys.stdin.read().split() in Python to read all input at once can reduce execution time.

• Leveraging binary search: If the coordinates \(X\) are sorted, the standard library’s bisect module can be used to quickly find the indices of elements within a specific range.

• Interval merging: After performing ranges.sort(), comparing the right endpoint of the current interval with the left endpoint of the next interval is a classic technique for solving interval problems.

  Source Code

import sys
from bisect import bisect_left, bisect_right

def main():
    # Read all input at once for fast processing
    # This is efficient for large inputs in Python
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Use a pointer to navigate through the input tokens
    ptr = 0
    N = int(input_data[ptr])
    M = int(input_data[ptr+1])
    ptr += 2
    
    # Parse treasure chest information: (position, coins)
    chests = []
    for _ in range(N):
        x = int(input_data[ptr])
        c = int(input_data[ptr+1])
        chests.append((x, c))
        ptr += 2
    
    # Sort chests by their coordinate X to allow binary search and prefix sums
    chests.sort()
    
    # Extract sorted coordinates and calculate prefix sums of coins
    # Prefix sums allow us to calculate the sum of coins in a coordinate range in O(1)
    X = [chest[0] for chest in chests]
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i+1] = prefix_sum[i] + chests[i][1]
        
    # Parse magic ranges [L, R]
    ranges = []
    for _ in range(M):
        l = int(input_data[ptr])
        r = int(input_data[ptr+1])
        ranges.append((l, r))
        ptr += 2
        
    # Sort magic ranges by their left boundary
    ranges.sort()
    
    # Merge overlapping or adjacent magic ranges to avoid counting the same chest multiple times
    # A chest's coins can only be collected once, so we need the union of all ranges.
    merged_ranges = []
    if M > 0:
        curr_l, curr_r = ranges[0]
        for i in range(1, M):
            next_l, next_r = ranges[i]
            if next_l <= curr_r:
                # Overlapping or touching ranges, update the right boundary
                if next_r > curr_r:
                    curr_r = next_r
            else:
                # Disjoint range found, store the current merged range and start a new one
                merged_ranges.append((curr_l, curr_r))
                curr_l, curr_r = next_l, next_r
        # Append the final merged range
        merged_ranges.append((curr_l, curr_r))
        
    # Calculate the total coins collected across all disjoint merged ranges
    total_coins = 0
    for l, r in merged_ranges:
        # Use binary search (bisect) to find the range of indices of chests within [l, r]
        # start_idx: first chest with X >= l
        # end_idx: first chest with X > r
        start_idx = bisect_left(X, l)
        end_idx = bisect_right(X, r)
        
        # Add the sum of coins for chests in this index range [start_idx, end_idx)
        if start_idx < end_idx:
            total_coins += prefix_sum[end_idx] - prefix_sum[start_idx]
            
    # Output the final result
    print(total_coins)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3-flash-thinking.