Overview

Given the results of dart throws and multiple bonus areas (intervals), the problem asks you to determine whether each throw lands within a bonus area and calculate the total score.

Analysis

Under the constraints of this problem, the number of throws \(N\) and the number of bonus areas \(M\) can both be up to \(2 \times 10^5\). A naive approach of checking all bonus areas one by one for each throw \(D_i\) (nested loops) would require up to \(N \times M = 4 \times 10^{10}\) operations, which would exceed the time limit (TLE).

To speed this up, the following two techniques are needed:

1. Interval Merging Bonus areas may overlap with each other. For example, if there are two areas \([1, 5]\) and \([3, 7]\), they can effectively be treated as a single larger area \([1, 7]\). By merging all overlapping intervals in advance, we can create a “collection of mutually non-overlapping, independent intervals.”

2. Fast Lookup Using Binary Search Once the intervals are non-overlapping, we can use binary search to quickly find which interval each \(D_i\) might belong to. This significantly reduces the time required for each lookup.

Algorithm

1. Sorting and Merging Intervals

   • Sort the given \(M\) bonus areas \([L_j, R_j]\) in ascending order of their left endpoints \(L_j\).
   • Iterate through the sorted intervals: if the current interval overlaps with the previous one, merge them; otherwise, add it as a new interval to the list (merged).
   • Example: If the sorted intervals are \([1, 5], [3, 7], [8, 10]\), then \([1, 5]\) and \([3, 7]\) overlap, so they are merged into \([1, 7]\). The resulting merged list becomes \([1, 7], [8, 10]\).

2. Creating the Left Endpoint List

   • To perform binary search, create a list L_list containing only the left endpoints of the merged intervals.
   • In the example above, L_list = [1, 8].

3. Calculating the Score for Each Throw

   • For each throw \(D_i\), perform a binary search (bisect_right) on L_list. This allows us to immediately find the interval with the largest left endpoint that is less than or equal to \(D_i\).
   • If the found interval is \([L, R]\) and \(D_i \leq R\) holds, then the dart is within a bonus area, and \(2 \times D_i\) is added to the score.
   • If it is not contained in any interval, the regular score \(D_i\) is added.

Complexity

• Time complexity: \(O((N + M) \log M)\)
  • Sorting the intervals takes \(O(M \log M)\).
  • Merging the intervals completes in \(O(M)\).
  • Binary search is performed for each of the \(N\) throws, taking \(O(N \log M)\).
  • Overall, this runs efficiently and comfortably fits within the constraints.
• Space complexity: \(O(N + M)\)
  • Used to store the throw data and the bonus area interval data.

Implementation Notes

• Usage of bisect_right Python’s bisect_right(A, x) returns the index where the first element greater than x would appear in array A. Therefore, to find the largest element less than or equal to x, you need to subtract 1 from the returned index. It is also important to check i >= 0 to ensure the result is not out of the array’s bounds.

• Overflow Considerations The dart distance \(D_i\) can be up to \(10^9\), and the total score can become very large (up to approximately \(4 \times 10^{14}\)). In Python, integers have no size limit so this is handled automatically, but when implementing in other languages such as C++, you need to use types like long long for the variable holding the total score.

• Fast I/O Since the input data can be very large, using sys.stdin.read().split() to read all input at once helps reduce the program’s execution time.

  Source Code

import sys
from bisect import bisect_right

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    D = [int(x) for x in input_data[2:2+N]]
    
    intervals = []
    idx = 2 + N
    for _ in range(M):
        L = int(input_data[idx])
        R = int(input_data[idx+1])
        intervals.append((L, R))
        idx += 2
        
    intervals.sort(key=lambda x: x[0])
    
    merged = []
    for L, R in intervals:
        if not merged:
            merged.append([L, R])
        else:
            if L <= merged[-1][1]:
                if R > merged[-1][1]:
                    merged[-1][1] = R
            else:
                merged.append([L, R])
                
    L_list = [x[0] for x in merged]
    
    total_score = 0
    for d in D:
        i = bisect_right(L_list, d) - 1
        if i >= 0 and merged[i][0] <= d <= merged[i][1]:
            total_score += d * 2
        else:
            total_score += d
            
    print(total_score)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3.1-pro-thinking.