Overview

Given distances \(D_i\), determine whether each falls within a bonus area. If it does, the score is \(2 \times D_i\); otherwise, the score is \(D_i\). Sum up all scores to get the total.

Analysis

The key to this problem is “efficiently determining whether each distance \(D_i\) falls within any of the \(M\) bonus areas.”

What about a naive approach?

The simplest approach is, for each \(D_i\), to check all bonus areas \((L_j, R_j)\) and see whether \(L_j \leq D_i \leq R_j\). This requires up to \(M\) comparisons for each \(D_i\), resulting in an overall complexity of \(O(N \times M)\).
Given the constraints, \(N, M\) can be up to \(2 \times 10^5\), so in the worst case this would require \(4 \times 10^{10}\) operations, which cannot be processed within the time limit (TLE).

Improvement idea

Since bonus areas are intervals (one-dimensional intervals), we can merge overlapping or adjacent intervals to create a “list of disjoint intervals.”
Since this list is sorted, we can use binary search to determine which interval a given value \(D_i\) falls into. This makes each query possible in \(O(\log M)\).

What is interval merging?

For example, the intervals \([1,3], [2,5], [6,7]\) can be merged into \([1,5], [6,7]\). By combining overlapping intervals in this way, subsequent searches become efficient.

Algorithm

1. First, collect all bonus area intervals \((L_j, R_j)\) and sort them in ascending order by their left endpoint \(L_j\).
2. Iterate through the sorted intervals from left to right, merging overlapping or adjacent intervals (adjacent means \(R_{prev} + 1 \geq L_{next}\)).
3. For each throw distance \(D_i\), perform a binary search on the merged interval list to determine whether there exists an interval containing \(D_i\).
4. If it is contained, add \(2 \times D_i\) to the score; otherwise, add \(D_i\).

Complexity

• Time complexity: \(O((N + M) \log M)\)
  • Sorting the intervals: \(O(M \log M)\)
  • Merging: \(O(M)\)
  • Binary search for each \(D_i\): \(O(N \log M)\)
• Space complexity: \(O(M + N)\)
  • Storing the intervals and holding the input

Implementation Notes

• Using the bisect module makes binary search easy to implement.

• The merging condition is: combine when the left endpoint of the current interval is less than or equal to (or +1 of) the right endpoint of the previous interval.

• To avoid errors even when there are no bonus areas, it is safe to include handling for empty lists.

  Source Code

import sys
from bisect import bisect_left, bisect_right

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    
    D = list(map(int, data[2:2+N]))
    
    intervals = []
    idx = 2 + N
    for _ in range(M):
        L = int(data[idx])
        R = int(data[idx+1])
        intervals.append((L, R))
        idx += 2
    
    # 区間をソート
    intervals.sort()
    
    # 区間のマージ
    if not intervals:
        merged = []
    else:
        merged = [list(intervals[0])]
        for L, R in intervals[1:]:
            last = merged[-1]
            if L <= last[1] + 1 - 1:  # L <= last[1] で重なりあり
                if R > last[1]:
                    merged[-1][1] = R
            else:
                merged.append([L, R])
    
    # 各D_iに対して、少なくとも一つの区間に含まれるかどうかを判定
    total = 0
    for d in D:
        # 二分探索で d が含まれるか判定
        # merged は [L,R] のリストでソートされている
        pos = bisect_right(merged, [d, float('inf')])  # L > d となる最初の位置
        # pos-1 が候補
        if pos > 0:
            L_prev, R_prev = merged[pos-1]
            if L_prev <= d <= R_prev:
                total += 2 * d
                continue
        # 次に pos
        if pos < len(merged):
            L_next, R_next = merged[pos]
            if L_next <= d <= R_next:
                total += 2 * d
                continue
        total += d
        
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.