結果

問題 No.2935 Division Into 3 (Mex Edition)
ユーザー 👑 potato167potato167
提出日時 2024-10-14 09:26:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 341 ms / 5,000 ms
コード長 2,548 bytes
コンパイル時間 2,505 ms
コンパイル使用メモリ 214,180 KB
実行使用メモリ 111,232 KB
最終ジャッジ日時 2024-10-14 09:26:20
合計ジャッジ時間 10,837 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 150 ms
108,800 KB
testcase_01 AC 151 ms
108,800 KB
testcase_02 AC 151 ms
108,816 KB
testcase_03 AC 218 ms
109,696 KB
testcase_04 AC 267 ms
110,464 KB
testcase_05 AC 281 ms
110,592 KB
testcase_06 AC 308 ms
110,592 KB
testcase_07 AC 268 ms
110,080 KB
testcase_08 AC 263 ms
110,208 KB
testcase_09 AC 294 ms
110,464 KB
testcase_10 AC 297 ms
110,464 KB
testcase_11 AC 217 ms
110,080 KB
testcase_12 AC 229 ms
109,768 KB
testcase_13 AC 299 ms
110,080 KB
testcase_14 AC 280 ms
110,464 KB
testcase_15 AC 288 ms
110,420 KB
testcase_16 AC 234 ms
110,080 KB
testcase_17 AC 341 ms
111,232 KB
testcase_18 AC 338 ms
111,196 KB
testcase_19 AC 301 ms
110,336 KB
testcase_20 AC 332 ms
110,208 KB
testcase_21 AC 266 ms
110,336 KB
testcase_22 AC 324 ms
110,336 KB
testcase_23 AC 332 ms
110,336 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 = 2500;
    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