結果

問題 No.2935 Division Into 3 (Mex Edition)
ユーザー 👑 potato167potato167
提出日時 2024-10-14 09:01:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3,609 ms / 5,000 ms
コード長 2,546 bytes
コンパイル時間 4,513 ms
コンパイル使用メモリ 213,584 KB
実行使用メモリ 13,184 KB
最終ジャッジ日時 2024-10-14 09:02:09
合計ジャッジ時間 57,616 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 24 ms
10,576 KB
testcase_01 AC 25 ms
10,752 KB
testcase_02 AC 24 ms
10,752 KB
testcase_03 AC 990 ms
11,776 KB
testcase_04 AC 1,809 ms
12,500 KB
testcase_05 AC 2,114 ms
12,544 KB
testcase_06 AC 2,176 ms
12,544 KB
testcase_07 AC 2,225 ms
11,904 KB
testcase_08 AC 2,165 ms
12,160 KB
testcase_09 AC 2,593 ms
12,372 KB
testcase_10 AC 2,691 ms
12,416 KB
testcase_11 AC 1,085 ms
12,032 KB
testcase_12 AC 1,037 ms
11,764 KB
testcase_13 AC 2,054 ms
12,032 KB
testcase_14 AC 2,301 ms
12,288 KB
testcase_15 AC 2,295 ms
12,288 KB
testcase_16 AC 1,187 ms
11,776 KB
testcase_17 AC 3,609 ms
13,056 KB
testcase_18 AC 3,602 ms
13,184 KB
testcase_19 AC 2,807 ms
12,032 KB
testcase_20 AC 3,413 ms
12,288 KB
testcase_21 AC 1,933 ms
12,160 KB
testcase_22 AC 3,457 ms
12,288 KB
testcase_23 AC 3,466 ms
12,288 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int INF=2100000000;
#define rep(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return 1;}else return 0;}


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

    int N;
    cin >> N;
    vector<int> A(N), C(N);
    rep(i, 0, N) cin >> A[i];
    const int D = 3;
    const int M = 100'001;
    vector<vector<int>> G(M);
    vector<int> ind(M, 3);
    rep(i, 0, M) rep(j, 0, D) G[i].push_back(-1);
    rep(i, 0, N){
        G[A[i]].push_back(i);
    }
    rep(i, 0, M) rep(j, 0, D) G[i].push_back(N);
    const int B = 46;
    vector<int> div_val(N + 1);
    vector<int> div_left(B + 1, INF);
    rep(i, 0, N + 1){
        div_val[i] = (i * B) / N;
        chmin(div_left[div_val[i]], i);
    }
    for (int i = B; i > 0; i--) chmin(div_left[i - 1], div_left[i]);
    vector pre(D, vector(B + 1, vector<int>(B + 1, INF)));
    vector val(D, vector<int>(B + 1, INF));
    rep(i, 0, D) rep(j, 0, M){
        chmin(val[i][div_val[G[j][3 + i]]], j);
    }
    int div_ind = 0;
    rep(i, 0, N + 1){
        while (div_ind != B + 1 && div_left[div_ind] == i){
            rep(j, 0, 3){
                pre[j][div_ind] = val[j];
                for (int k = B; k > 0; k--){
                    chmin(pre[j][div_ind][k - 1], pre[j][div_ind][k]);
                }
            }
            div_ind++;
        }
        if (i == N) break;
        C[i] = ind[A[i]];
        ind[A[i]]++;
        rep(j, 0, D){
            chmin(val[j][div_val[G[A[i]][ind[A[i]] + j]]], A[i]);
        }
    }
    int Q;
    cin >> Q;
    ll F = 0;
    rep(rp, 0, Q){
        ll l, r;
        cin >> l >> r;
        l ^= F, r ^= F;
        l--;
        vector<int> ans(3);
        rep(i, 0, 3){
            ans[i] = pre[i][div_val[l]][div_val[r - 1] + 1];
        }
        int L = div_left[div_val[l]];
        int R = div_left[div_val[r - 1] + 1];
        while (L < l){
            rep(j, 0, D){
                if (G[A[L]][C[L] + j + 1] >= R){
                    chmin(ans[j], A[L]);
                }
            }
            L++;
        }
        while (r < R){
            R--;
            rep(j, 0, D){
                if (G[A[R]][C[R] - j - 1] < L){
                    chmin(ans[j], A[R]);
                }
            }
        }
        F = 0;
        int tmp = 0;
        rep(i, 0, 3){
            F += ans[i];
            if (ans[i] == 0) tmp++;
        }
        chmin(F, r - l - tmp);
        cout << F << "\n";
    }
}
0