結果

問題 No.3801 Split Pairs
コンテスト
ユーザー GOTKAKO
提出日時 2026-11-13 23:46:55
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 166 ms / 2,000 ms
+ 487µs
コード長 4,861 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,156 ms
コンパイル使用メモリ 228,444 KB
実行使用メモリ 16,640 KB
最終ジャッジ日時 2026-11-13 23:47:04
合計ジャッジ時間 6,363 ms
ジャッジサーバーID
(参考情報)
judge2_0 / judge1_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

#include <bits/stdc++.h>
using namespace std;

template<typename T=long long>
struct IntervalSet{ //区間をsetで管理するテク~
    T len;
    set<pair<T,T>> S;
    IntervalSet():len(0){}
    T add(T l,T r){ //[l,r]を追加.
        auto memolen = len;
        assert(l <= r);
        auto itr = S.lower_bound({l,-1});
        if(itr != S.begin()) itr--;
        vector<pair<T,T>> Era;
        while(itr != S.end()){
            auto [L,R] = *itr; itr++;
            if(R+1 < l) continue; 
            if(r+1 < L) break;
            len -= R-L+1,Era.push_back({L,R});
            l = min(l,L),r = max(r,R);
        }
        for(auto e : Era) S.erase(e);
        len += r-l+1,S.insert({l,r});
        return len-memolen; //追加した区間長.
    }
    T era(T l,T r){ //[l,r]を削除.
        auto memolen = len;
        assert(l <= r);
        auto itr = S.lower_bound({l,-1});
        if(itr != S.begin()) itr--;
        vector<pair<T,T>> Era,Add;
        while(itr != S.end()){
            auto [L,R] = *itr; itr++;
            if(R < l) continue;
            if(r < L) break;
            len -= R-L+1,Era.push_back({L,R});
            if(L < l) Add.push_back({L,l-1});
            if(r < R) Add.push_back({r+1,R});
        }
        for(auto e : Era) S.erase(e);
        for(auto a : Add) S.insert(a);
        for(auto [L,R] : Add) len += R-L+1;
        return memolen-len; //削除した区間長.
    }  
    vector<pair<T,T>> add2(T l,T r){ //[l,r]を追加 追加した区間を返す.
        assert(l <= r);
        auto itr = S.lower_bound({l,-1});
        if(itr != S.begin()) itr--;
        vector<pair<T,T>> Era,ret;
        long long al = l,ar = r;
        while(itr != S.end()){
            auto [L,R] = *itr; itr++;
            if(R+1 < l) continue; 
            if(r+1 < L) break;
            len -= R-L+1,Era.push_back({L,R});
            if(al < L) ret.push_back({al,L-1});
            l = min(l,L),r = max(r,R),al = R+1;
        }
        for(auto e : Era) S.erase(e);
        len += r-l+1,S.insert({l,r});
        if(al <= ar) ret.push_back({al,ar});
        return ret;
    }
    vector<pair<T,T>> era2(T l,T r){ //[l,r]を削除 削除した区間を返す.
        assert(l <= r);
        auto itr = S.lower_bound({l,-1});
        if(itr != S.begin()) itr--;
        vector<pair<T,T>> Era,Add,ret;
        while(itr != S.end()){
            auto [L,R] = *itr; itr++;
            if(R < l) continue;
            if(r < L) break;
            len -= R-L+1,Era.push_back({L,R});
            T dl = L,dr = R;
            if(L < l) Add.push_back({L,l-1}),dl = l;
            if(r < R) Add.push_back({r+1,R}),dr = r;
            ret.push_back({dl,dr});
        }
        for(auto e : Era) S.erase(e);
        for(auto a : Add) S.insert(a);
        for(auto [L,R] : Add) len += R-L+1;
        return ret;
    }  
    pair<vector<pair<T,T>>,vector<pair<T,T>>> add3(T l,T r){ //[l,r]を追加 変わった区間を返す.
        assert(l <= r);
        auto itr = S.lower_bound({l,-1});
        if(itr != S.begin()) itr--;
        vector<pair<T,T>> Era;
        while(itr != S.end()){
            auto [L,R] = *itr; itr++;
            if(R+1 < l) continue; 
            if(r+1 < L) break;
            len -= R-L+1;
            Era.push_back({L,R});
            l = min(l,L),r = max(r,R);
        }
        for(auto e : Era) S.erase(e);
        len += r-l+1,S.insert({l,r});
        return {{{l,r}},Era};
    }
    pair<vector<pair<T,T>>,vector<pair<T,T>>> era3(T l,T r){ //[l,r]を削除 変わった区間を返す.
        assert(l <= r);
        auto itr = S.lower_bound({l,-1});
        if(itr != S.begin()) itr--;
        vector<pair<T,T>> Era,Add;
        while(itr != S.end()){
            auto [L,R] = *itr; itr++;
            if(R < l) continue;
            if(r < L) break;
            len -= R-L+1,Era.push_back({L,R});
            if(L < l) Add.push_back({L,l-1});
            if(r < R) Add.push_back({r+1,R});
        }
        for(auto e : Era) S.erase(e);
        for(auto a : Add) S.insert(a);
        for(auto [L,R] : Add) len += R-L+1;
        return {Add,Era};
    }  
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; cin >> N;
    vector<int> A(N);
    for(auto &a : A) cin >> a;


    IntervalSet S;
    long long answer = 0;
    for(auto a : A){
        auto itr = S.S.lower_bound({a+1,-1});
        if(itr == S.S.begin()) S.add(a,a);
        else{
            itr--;
            auto [l,r] = *itr;
            if(l <= a && a <= r){
                S.era(l,r);
                long long left = a-l+1,right = r-a+1,len = r-l+1,len2 = len+2-2*min(left,right);
                answer += (len+len2)*min(left,right)/2;
                S.add(l-1,l-1+right-1),S.add(r+1-left+1,r+1);
            }
            else S.add(a,a);
        }
    }
    cout << answer << endl;
}
0