Overview

We need to efficiently determine whether each distance \(D_i\) falls within any bonus interval \([L_j, R_j]\), and for each throw that does, add an extra \(D_i\) points to the total score.

Analysis

The score for each throw is \(2D_i\) if it lands in a bonus area, and \(D_i\) otherwise. Therefore, the total score can be computed as: - First, sum up \(D_i\) for all throws (the base score). - Then, for each throw that lands in a bonus area, “add an extra \(D_i\).”

This simplifies the problem.

The core challenge is determining whether \(D_i\) is contained in any of the \(M\) intervals, and doing this \(N\) times.

Why the naive approach is too slow

If we check all intervals \([L_j, R_j]\) for each \(D_i\), the worst case is \(O(NM)\). Since \(N, M \le 2\times 10^5\), this would be on the order of \(4\times 10^{10}\) operations, which is too slow.

How to solve it (key insight)

Even if intervals overlap, we only need to know “whether \(D_i\) is inside any of them.” Therefore, if we sort the bonus intervals and merge overlapping ones in advance, we obtain a sequence of non-overlapping intervals.

Example: - \([1, 5], [3, 7], [10, 12]\) after merging becomes - \([1, 7], [10, 12]\)

Once the intervals are non-overlapping, we can use binary search to quickly find which interval each \(D_i\) might belong to.

Algorithm

1. Sort the \(M\) input intervals \([L_j, R_j]\) in ascending order of \(L_j\).
2. Scan from left to right, merging overlapping (or adjacent) intervals to create a non-overlapping interval sequence merged.
   • If the left endpoint \(l\) of the new interval is greater than the right endpoint of the previous interval (\(l > prev\_r\)), add it as a separate interval.
   • Otherwise, they overlap, so extend the right endpoint to \(\max(prev\_r, r)\).
3. Extract starts (left endpoints of each interval) and ends (right endpoints of each interval) as arrays from merged.
4. Compute the total score as follows:
   • total = sum(Ds) (base score for all throws)
   • For each \(d \in Ds\), perform a binary search on starts to find “the interval with the largest start that is \(\le d\).” Specifically, k = bisect_right(starts, d) - 1.
   • If \(k \ge 0\) and \(d \le ends[k]\), then \(d\) is contained in that interval, so add the bonus: extra += d.
   • Output total + extra as the final answer.

Why this check is correct: - starts is sorted in ascending order and the intervals are non-overlapping, so the only interval that could contain \(d\) is “the one with the largest start point that is \(\le d\).” - If \(d\) is within that interval’s right endpoint ends[k], it is inside; otherwise, it is outside.

Complexity

• Time complexity: \(O(M\log M)\) for sorting the intervals and \(O(N\log M)\) for checking each throw, giving \(O((N+M)\log M)\) overall.
• Space complexity: \(O(M)\) for the interval arrays and merge results.

Implementation Notes

• By merging intervals in advance, each check becomes just “one binary search + one comparison.”

• The result of bisect_right(starts, d) - 1 can be -1 (i.e., all start values are greater than \(d\)), so a k >= 0 check is necessary.

• The maximum score is at most \(2 \times \sum D_i\), so there is no overflow concern with Python’s int.

• Since the input can be large, it is safer to read it quickly using sys.stdin.buffer.read() as shown in the provided code.

  Source Code

import sys
from bisect import bisect_right

def main():
    data = sys.stdin.buffer.read()
    ndata = len(data)
    idx = 0

    def ni():
        nonlocal idx
        while idx < ndata and data[idx] <= 32:
            idx += 1
        num = 0
        while idx < ndata and data[idx] > 32:
            num = num * 10 + (data[idx] - 48)
            idx += 1
        return num

    N = ni()
    M = ni()
    Ds = [ni() for _ in range(N)]
    intervals = [(ni(), ni()) for _ in range(M)]

    intervals.sort()
    merged = []
    for l, r in intervals:
        if not merged or l > merged[-1][1]:
            merged.append([l, r])
        else:
            if r > merged[-1][1]:
                merged[-1][1] = r

    starts = [lr[0] for lr in merged]
    ends = [lr[1] for lr in merged]

    total = sum(Ds)
    extra = 0
    for d in Ds:
        k = bisect_right(starts, d) - 1
        if k >= 0 and d <= ends[k]:
            extra += d

    print(total + extra)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.