Overview

This problem requires determining, for each dart throw distance, whether that distance falls within any bonus area, calculating the score accordingly, and summing up the total.

Analysis

For each throw distance \(D_i\), we need to determine whether it is contained in any bonus area \([L_j, R_j]\). A naive approach would check all bonus areas (\(M\) of them) for each \(D_i\), resulting in a time complexity of \(O(N \times M)\). Since \(N\) and \(M\) can each be up to \(2 \times 10^5\), this would require up to \(4 \times 10^{10}\) checks, which cannot be processed within the time limit.

Therefore, we need a way to efficiently manage the bonus areas and quickly determine whether each \(D_i\) falls within a bonus area. The bonus areas form a collection of intervals, and by computing their union, we can identify the contiguous intervals that the bonus areas cover. Since bonus areas may overlap, taking the union may split them into multiple contiguous intervals (segments). If we precompute these segments, we can use binary search to quickly determine whether each \(D_i\) is contained in any of these segments.

Algorithm

1. Computing the union of bonus areas:

   • For each bonus area \([L_j, R_j]\), create an event of +1 at the start point \(L_j\) and -1 at the end point \(R_j+1\).
   • Sort these events in ascending order of coordinate.
   • Process the sorted events sequentially, maintaining a counter of the number of active intervals. While the counter is positive, the bonus area is contiguous, so we record union segments accordingly.

2. Determining each throw distance:

   • The list of segments obtained from the previous step is a sorted collection of contiguous intervals.
   • For each \(D_i\), perform a binary search on the segment list to determine whether \(D_i\) is contained in any segment.
   • If it is contained, add \(2 \times D_i\) to the total score; otherwise, add \(D_i\).

Complexity

• Time complexity: \(O(M \log M + N \log M)\)
  • Sorting events: \(O(M \log M)\)
  • Building segments: \(O(M)\)
  • Binary search for each \(D_i\): \(O(\log M)\) each, totaling \(O(N \log M)\)
• Space complexity: \(O(M)\)
  • The event list and segment list each have size \(O(M)\)

Implementation Notes

• During event processing, a sweep line algorithm is used to compute the union of intervals. Since a segment ends when the counter transitions from positive to 0, the end point event must be registered at \(R_j+1\).

• The segment list is sorted in ascending order, making binary search applicable. Each segment is represented as a \((start, end)\) tuple, and we check whether \(D_i\) satisfies \(start \leq D_i \leq end\).

• sys.stdin.read is used for input to efficiently handle large amounts of data.

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx]); M = int(data[idx+1]); idx += 2
    D_list = list(map(int, data[idx:idx+N]))
    idx += N
    intervals = []
    for _ in range(M):
        L = int(data[idx]); R = int(data[idx+1]); idx += 2
        intervals.append((L, R))
    
    events = []
    for L, R in intervals:
        events.append((L, 1))
        events.append((R+1, -1))
    
    events.sort(key=lambda x: x[0])
    
    current = 0
    active_intervals = 0
    last_pos = 0
    segments = []
    for pos, delta in events:
        if active_intervals > 0:
            segments.append((last_pos, pos-1))
        active_intervals += delta
        last_pos = pos
    
    total_score = 0
    for d in D_list:
        low, high = 0, len(segments) - 1
        found = False
        while low <= high:
            mid = (low + high) // 2
            seg_start, seg_end = segments[mid]
            if seg_start <= d <= seg_end:
                found = True
                break
            elif d < seg_start:
                high = mid - 1
            else:
                low = mid + 1
        
        if found:
            total_score += 2 * d
        else:
            total_score += d
    
    print(total_score)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.