Overview

This problem requires determining whether the distance of each throw falls within a bonus area (a ring-shaped region), and if so, doubling the score for that throw, then computing the total score.

Analysis

Naive Approach and Its Issues

The simplest method is, for each throw \(D_i\), to check all \(M\) bonus areas in order to determine “is there some \(j\) such that \(L_j \leq D_i \leq R_j\)?” However, this method requires up to \(M\) checks per throw, resulting in an overall time complexity of \(O(N \times M)\). When \(N, M\) are at most \(2 \times 10^5\), this requires up to \(4 \times 10^{10}\) operations in the worst case, leading to TLE (Time Limit Exceeded).

Key Observations

1. Merging Bonus Areas: Bonus areas may overlap with each other, but since we only care about whether a given distance falls within any bonus area, we can merge overlapping or adjacent intervals into one. For example, \([2, 5]\) and \([4, 8]\) can be merged into \([2, 8]\).

2. Fast Lookup via Binary Search: After merging, the intervals are non-overlapping and sorted by their left endpoints. Therefore, we can determine whether a distance \(d\) falls within any interval using binary search in \(O(\log M)\).

Algorithm

Step 1: Merging Intervals

1. Sort the \(M\) bonus areas \([L_j, R_j]\) in ascending order of their left endpoints \(L_j\).
2. Iterate through the sorted intervals, merging each one with the previous interval if they overlap or are adjacent. Specifically, if the current interval’s \(L\) is at most the previous merged interval’s \(R + 1\), update the previous interval’s \(R\) to \(\max(R_{\text{prev}}, R_{\text{current}})\).

Example: \([1, 5], [3, 7], [10, 15]\) → After merging: \([1, 7], [10, 15]\)

Step 2: Checking Each Throw

For each \(D_i\):

1. Using the array starts of left endpoints of the merged intervals, compute the index pos of “the last interval whose left endpoint is at most \(d\)” via bisect_right(starts, d) - 1.
2. If pos >= 0 and d <= ends[pos], then \(D_i\) falls within a bonus area, so the score is \(2 \times D_i\).
3. Otherwise, the score is \(D_i\).

Why this is correct: Since the merged intervals are non-overlapping and sorted, the only interval that could contain \(d\) is “the rightmost interval whose left endpoint is at most \(d\).” If that interval’s right endpoint is at least \(d\), then \(d\) is contained within it.

Complexity

• Time complexity: \(O(M \log M + N \log M)\)
  • Sorting intervals: \(O(M \log M)\)
  • Binary search for each throw: \(O(\log M)\), repeated \(N\) times for \(O(N \log M)\)
• Space complexity: \(O(N + M)\)
  • Storing throw data and merged intervals

Implementation Notes

• Interval merging condition: Since the values are integers, we use \(L \leq R_{\text{prev}} + 1\) to also merge adjacent intervals (e.g., \([1,3]\) and \([4,6]\) become \([1,6]\)). However, for this problem, since the checks use “greater than or equal to” and “less than or equal to,” not merging adjacent intervals would still yield correct results.

• Usage of bisect_right: bisect_right(starts, d) - 1 gives the rightmost index among intervals whose left endpoint is at most \(d\). If the result is \(-1\) (no such interval exists), the throw is outside any bonus area.

• Potentially large output: Since \(D_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the total can be as large as approximately \(4 \times 10^{14}\). Python handles this naturally with arbitrary-precision integers, but in other languages, a 64-bit integer type must be used.

  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
    D = [int(input_data[idx + i]) for i in range(N)]; idx += N
    
    # Read bonus areas and merge them
    intervals = []
    for j in range(M):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        intervals.append((L, R))
    
    # Merge overlapping intervals
    intervals.sort()
    merged = []
    for L, R in intervals:
        if merged and L <= merged[-1][1] + 1:
            merged[-1] = (merged[-1][0], max(merged[-1][1], R))
        else:
            merged.append((L, R))
    
    # For each D_i, check if it falls in any merged interval using binary search
    # merged is sorted by start. For a query d, find the rightmost interval whose start <= d,
    # then check if d <= that interval's end.
    starts = [m[0] for m in merged]
    ends = [m[1] for m in merged]
    
    total = 0
    for d in D:
        # Find the index of the last interval with start <= d
        pos = bisect_right(starts, d) - 1
        if pos >= 0 and d <= ends[pos]:
            total += 2 * d
        else:
            total += d
    
    print(total)

main()

---

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