概要

距離 \(D_i\) が「どれか1つでもボーナス区間 \([L_j, R_j]\) に入るか」を高速に判定し、入る投擲だけ \(D_i\) 点ぶん加算して合計点を求めます。

考察

各投擲の得点は、ボーナスエリア内なら \(2D_i\)、外なら \(D_i\) です。したがって合計点は - まず全投擲ぶんの \(D_i\) を合計し（外側の基本点） - ボーナスエリア内に入った投擲について「追加で \(D_i\) を足す」 と考えると簡単です。

問題は「\(D_i\) が \(M\) 個の区間のどれかに含まれるか」を \(N\) 回判定する部分です。

素朴な方法が遅い理由

各 \(D_i\) について全ての区間 \([L_j, R_j]\) を調べると、最悪で \(O(NM)\) になります。
\(N, M \le 2\times 10^5\) なので、\(4\times 10^{10}\) 回規模となり間に合いません。

どう解決するか（重要な気づき）

区間が重なっていても、「入っているかどうか」だけが必要です。
そこで、ボーナス区間をあらかじめ ソートして重なりをマージ（統合） しておくと、互いに重ならない区間列になります。

例： - \([1, 5], [3, 7], [10, 12]\)
をマージすると - \([1, 7], [10, 12]\) のように減ります。

互いに重ならない区間になれば、各 \(D_i\) について「どの区間に入り得るか」を二分探索で高速に探せます。

アルゴリズム

1. 入力された \(M\) 個の区間 \([L_j, R_j]\) を \(L_j\) の昇順でソートする。
2. 左から順に見て、重なる（または接する）区間をマージして、互いに重ならない区間列 merged を作る。
   • 新しい区間の左端 \(l\) が、直前の区間の右端より大きい（\(l > prev\_r\)）なら別区間として追加
   • そうでなければ重なるので右端を \(\max(prev\_r, r)\) に伸ばす
3. merged から starts（各区間の左端）と ends（各区間の右端）を配列として取り出す。
4. 合計点を次のように計算する：
   • total = sum(Ds)（全投擲の基本点）
   • 各 \(d \in Ds\) について、starts に対して二分探索し「\(d\) 以下の最大の start を持つ区間」を探す
     具体的には k = bisect_right(starts, d) - 1。
   • \(k \ge 0\) かつ \(d \le ends[k]\) なら、その区間に含まれるのでボーナス分として extra += d。
   • 最終的に total + extra を出力。

この判定が正しい理由： - starts は昇順で、区間は互いに重ならないので、\(d\) が入る可能性があるのは「開始点が \(d\) 以下の中で最も右にある区間」だけです。 - その区間の右端 ends[k] まで届いていれば内側、届かなければ外側です。

計算量

• 時間計算量: 区間ソートに \(O(M\log M)\)、各投擲の判定に \(O(N\log M)\) なので全体で \(O((N+M)\log M)\)
• 空間計算量: 区間配列やマージ結果などで \(O(M)\)

実装のポイント

• 区間のマージをしておくことで、判定が「二分探索 + 1回の比較」になります。

• bisect_right(starts, d) - 1 の結果が -1（つまり全ての start が \(d\) より大きい）になる場合があるので、k >= 0 チェックが必要です。

• 得点は最大で \(2 \times \sum D_i\) なので、Python の int ならオーバーフローの心配はありません。

• 入力が大きいので、提示コードのように sys.stdin.buffer.read() で高速に読むと安全です。

  ソースコード

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()

---

この解説は gpt-5.2-high によって生成されました。