イベントソート と呼ばれる手法でこの問題に正解できます。

区間 \([l,r]\) に貼られたテープを以下の \(2\) つのイベントに言い換えます。

• 座標 \(l\) にて、テープが \(1\) 本始まる。
• 座標 \(r\) にて、テープが \(1\) 本終わる。

座標の小さい方から調べて、 (それまでに始まったテープの本数) \(>\) (それまでに終わったテープの本数) が成り立てば、その区間にテープが貼られています。

総合すると、以下の解法が成り立ちます。

• 連想配列 \(mp\) を用意する。
• \(i=1,2,\dots,N\) について、以下を繰り返す。
  • \(mp[l_i]\) に \(1\) 加算する。
  • \(mp[l_i+w_i]\) から \(1\) 減算する。
• その後、 \(mp\) の添え字の昇順に調べる。今伸びているテープの本数 \(h=0\) 、直前の座標 \(pre = -\infty\) と初期化する。
  • 現在着目している要素が \(mp[x]=y\) とする。
  • \(h>0\) であれば、座標 \(pre\) から座標 \(x\) までに少なくとも一本のテープが貼られていることが分かるので、答えに \(x-pre\) を加算する。
  • \(h\) に \(y\) 加算する。
  • 直前の座標 \(pre=x\) に更新する。

連想配列を使わなくとも、イベントを配列として座標の昇順にソートする方法でもこの問題に正解できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N,W;
  cin >> N >> W;
  map<int,int> mp;
  for(int i=0;i<N;i++){
    int l,w;
    cin >> l >> w;
    mp[l]++;
    mp[l+w]--;
  }

  int res=0;
  int h=0,pre=-1;
  for(auto &nx : mp){
    if(h>0){
      res+=(nx.first-pre);
    }
    h+=nx.second;
    pre=nx.first;
  }
  cout << res << "\n";
  return 0;
}