結果

問題 No.3063 Circle Balancing
コンテスト
ユーザー rin204
提出日時 2024-07-07 17:09:27
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 313 ms / 3,000 ms
コード長 1,465 bytes
コンパイル時間 2,878 ms
コンパイル使用メモリ 254,572 KB
実行使用メモリ 37,052 KB
最終ジャッジ日時 2024-07-07 17:09:37
合計ジャッジ時間 9,351 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#include "atcoder/segtree.hpp"

struct S {
    int x22;
    int x20;
    int x00;
    int le;
};
S op(S l, S r) {
    S ret;
    ret.x22 = l.x22 + r.x22;
    ret.x20 = min({l.x22 + r.x20, l.x22 + r.x00, l.x20 + r.x00});
    ret.x00 = l.x00 + r.x00;
    ret.le  = l.le + r.le;
    return ret;
}
S e() {
    return {0, 0, 0, 0};
}

int main() {
    int n;
    cin >> n;
    assert(1 <= n and n <= 300000);
    vector<vector<int>> pos(n);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        assert(1 <= a and a <= n);
        pos[a - 1].push_back(i);
    }

    S e2 = {0, 0, 1, 1};
    S e0 = {1, 0, 0, 1};

    vector<S> ini(n, e2);
    atcoder::segtree<S, op, e> seg(ini);
    int ans = 1 << 30;
    for (int i = 0; i < n; i++) {
        if (pos[i].empty()) continue;
        int tot = 0;

        for (int j = 0; j < pos[i].size() - 1; j++) {
            int l    = pos[i][j] + 1;
            int r    = pos[i][j + 1];
            auto res = seg.prod(l, r);
            tot += min({res.x22, res.x20, res.x00}) + res.le;
        }
        {
            auto res1 = seg.prod(pos[i].back() + 1, n);
            auto res2 = seg.prod(0, pos[i].front());
            auto res  = op(res1, res2);
            tot += min({res.x22, res.x20, res.x00}) + res.le;
        }
        ans = min(ans, tot);

        for (auto p : pos[i]) {
            seg.set(p, e0);
        }
    }
    cout << ans << endl;
}
0