D - Online games

問題

個の区間が与えられる。個の区間が重複していた数を答えよ。
atcoder.jp

解法

まず最も簡単な愚直な解法を考えてみる。
の区間をすべて全探索してしまい、かぶっている区間の数を数え上げて、最後にそれを答えとしてしまえば良い。
この解法はTLEとなる。そこで少し工夫を加える。
重要な考察として、重複している区間の数が変化するのは、与えられた区間の左端と右端のみである。そのため、入力となる個の区間のみをつかって答えを探していけばよい。

ここまで見ると、区間スケジューリングに近いなという感じがする。
(実は区間スケジューリングで問題を解こうとしていた。始点でソートするとうまくいきそうな気がするか、うまく行かなかった。うまく行ったとしても、めちゃくちゃ大変な実装を要求されそう。)

ただし、今回は区間で見る必要はなく、単純に左端と右端をソートし、単に数え上げるだけで良い

#include <vector>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <set>
#include <tuple>
#include <map>

using namespace std;
using Int = long long;


int main()
{
    Int N; cin >> N;
    vector<tuple<Int,int>>v;
    set<tuple<Int,int>>S;
    
    for(int i = 0; i < N; ++i)
    {
        Int A,B;
        cin >> A >> B;
        v.emplace_back(A,0); v.emplace_back(A + B,1);
    }
    
    vector<Int>ans(N + 1,0);
    Int crt = 0;
    Int key = 0;
    
    sort(v.begin(),v.end());
    
    for(auto [e, type] : v)
    {
        if(type == 0)
        {
            Int prev = e - crt;
            ans[key] += prev;
            ++key; crt = e;
        }
        else
        {
            Int prev = e - crt;
            ans[key] += prev;
            --key; crt = e;
            
        }
    }
    
    for(int i = 1; i < ans.size(); ++i)
    {
        if(i != 1)
            cout << " ";
        cout << ans[i];
    }
    
    
    cout << endl;
}