abc355 D - Intersecting Intervals [left, right]でソートする解法

• 問題 https://atcoder.jp/contests/abc355/tasks/abc355_d
• AC https://atcoder.jp/contests/abc355/submissions/56180179
• 解説とは違う解法だったので書いておく
• ペア [left, right]の配列をソートする
• それぞれのペアから見て、自身より後ろを見て、どこかまでは共通部分があり、それより後は共通部分がない。という性質があるので切れ目を二分探索できる

画像

• 丸1がイメージ
• 丸2のような入力でも通るようにしよう

code抜粋

using ll = long long;
using PII = pair<ll, ll>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N;
    cin>>N;
    
    vector<PII> V;
    rep(i,N){
      ll l,r;cin>>l>>r;
      V.push_back({l,r});
    }
    sort(ALL(V));

    debug(V);
    ll cnt=0;
    rep(i,N-1){
      ll l=V[i].first;
      ll r=V[i].second;

      // 1つ右は重なっているか？
      if(r < V[i+1].first)continue;

      // 重なっている場合
      ll ok=i+1;
      ll ng=N;
      while(ng-ok>1){
        ll center = (ok+ng)/2;
        if(V[center].first<=r){
          ok=center;
        }else{
          ng=center;
        }
      }
      cnt += ok-i;
    }

    p(cnt);
    return 0;
}