結果

問題 No.3063 Circle Balancing
ユーザー tute7627
提出日時 2024-07-06 23:39:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 442 ms / 3,000 ms
コード長 1,123 bytes
コンパイル時間 2,189 ms
コンパイル使用メモリ 202,964 KB
最終ジャッジ日時 2025-03-13 01:12:18
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct M{
    int v0, v2, v20;
};

M op(M a, M b){
    M res;
    res.v0 = a.v0 + b.v0;
    res.v2 = a.v2 + b.v2;
    res.v20 = max({a.v20 + b.v0, a.v2 + b.v20, a.v2 + b.v0});
    return res;
}

M e(){
    return {0, 0, 0};
}


int main(){
    int N;cin >> N;
    assert(1 <= N && N <= 300000);
    vector<int> A(N);
    vector<vector<int>> Ai(N);
    for(int i = 0; i < N; i++){
        cin >> A[i];
        assert(1 <= A[i] && A[i] <= N);
        Ai[A[i]-1].push_back(i);
    }

    atcoder::segtree<M, op, e> seg(vector<M>(2*N, {0, 1, 1}));
    int ans = INT_MAX;
    for(int i = 0; i < N; i++){
        if(Ai[i].size() == 0) continue;
        int res = (N - Ai[i].size()) * 2;
        for(int j = 0; j < Ai[i].size(); j++){
            int l = Ai[i][j], r = Ai[i][(j+1)%Ai[i].size()];
            if(l >= r)r += N;
            res -= seg.prod(l + 1, r).v20;
        }
        for(auto idx: Ai[i]){
            seg.set(idx, {1, 0, 1});
            seg.set(idx + N, {1, 0, 1});
        }
        ans = min(ans, res);
    }
    cout << ans << endl;
}
0