AI 解説は区間をデータ構造で管理してマージする手法を取っていますが、本解説ではそれを回避します。
B 問題同様、 C 問題も イベントソート で解くことができます。

ダーツの得点計算をする際に起きることを以下の整数組で表現します。

• \((L_i,0)\) … 距離 \(L_i\) にてボーナスエリアが \(1\) つ開始する。
• \((D_i,1)\) … 距離 \(D_i\) のダーツの得点を計算する。
• \((R_i,2)\) … 距離 \(R_i\) にてボーナスエリアが \(1\) つ終了する。

この整数組を辞書順にソートします。すると、得点計算は以下のように行えます。

• はじめ、現在かかっているボーナスエリアの個数 \(h=0\) とする。
• 整数組 \((d,typ)\) が出てきたとする。
  • \(typ=0\) ならボーナスエリアが \(1\) つ開始するため、 \(h\) に \(1\) 加算する。
  • \(typ=1\) なら距離 \(d\) にダーツが存在するので、そのダーツの得点を計算する。もし \(h=0\) ならボーナスエリアにかかっていないため得点は \(d\) 、そうでなければボーナスエリアにかかっているため得点は \(2d\) である。
  • \(typ=2\) ならボーナスエリアが \(1\) つ終了するため、 \(h\) から \(1\) 減算する。

小技として、開始を \(0\) 、得点計算を \(1\) 、終了を \(2\) と番号付けして整数組を辞書順に並べることで、ボーナスエリアの境界に当たったダーツの得点計算も正しく行うことができます。

時間計算量は \(O((N+M) \log (N+M))\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N,M;
  cin >> N >> M;
  vector<pair<ll,ll>> ev;
  for(ll i=0;i<N;i++){
    ll D;
    cin >> D;
    ev.push_back({D,1});
  }
  for(ll i=0;i<M;i++){
    ll L,R;
    cin >> L >> R;
    ev.push_back({L,0});
    ev.push_back({R,2});
  }
  sort(ev.begin(),ev.end());
  ll res=0;
  ll h=0;
  for(auto [d,typ] : ev){
    if(typ==0){h++;}
    else if(typ==1){
      if(h>0){res+=2*d;}
      else{res+=d;}
    }
    else{h--;}
  }
  cout << res << "\n";
  return 0;
}