結果

問題 No.2935 Division Into 3 (Mex Edition)
コンテスト
ユーザー askr58
提出日時 2024-10-13 05:57:51
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,762 bytes
コンパイル時間 8,208 ms
コンパイル使用メモリ 352,968 KB
実行使用メモリ 306,948 KB
最終ジャッジ日時 2024-10-13 05:58:07
合計ジャッジ時間 14,955 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using ll=long long;
using mint=modint998244353;
const int b=650;
using ar=array<int,3>;
int d,w;
ll op(ll x,ll y){
    return min(x,y);
}
ll e(){
    return 1e9;
}

bool F(ll x){
    return x>=d;
}
int main()
{
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)a[i]=min(a[i],n);
    vector<vector<segtree<ll,op,e>>> stv((n+b)/b,vector<segtree<ll,op,e>>(3));
    for(int i=0;i<3;i++)stv[0][i]=segtree<ll,op,e>(vector<ll>(n+1,-1));
    for(int i=1;i<(n+b)/b;i++){
        stv[i]=stv[i-1];
        for(int j=(i-1)*b;j<min(n,i*b);j++){
            stv[i][2].set(a[j],stv[i][1].get(a[j]));
            stv[i][1].set(a[j],stv[i][0].get(a[j]));
            stv[i][0].set(a[j],j);
        }
    }
    ll key=0;
    int q;
    cin>>q;
    while(q--){
        ll x,y;
        cin>>x>>y;
        x^=key;y^=key;
        x--;
        int p=y/b;
        vector<ll> rec;
        for(int i=p*b;i<y;i++){
            rec.push_back(stv[p][2].get(a[i]));
            stv[p][2].set(a[i],stv[p][1].get(a[i]));
            stv[p][1].set(a[i],stv[p][0].get(a[i]));
            stv[p][0].set(a[i],i);
        }
        int ans=0;
        for(int i=0;i<3;i++){
            d=x;
            ans+=min((ll)(stv[p][i].max_right<F>(0)),y-x-2);
        }
        cout<<ans<<endl;
        key=ans;
        reverse(rec.begin(),rec.end());
        for(int i=y-1;i>=p*b;i--){
            int j=y-1-i;
            stv[p][0].set(a[i],stv[p][1].get(a[i]));
            stv[p][1].set(a[i],stv[p][2].get(a[i]));
            stv[p][2].set(a[i],rec[j]);
        }
    }

    
    return 0;
}
0