結果

問題 No.2935 Division Into 3 (Mex Edition)
コンテスト
ユーザー nouka28
提出日時 2024-09-24 06:44:07
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,673 ms / 5,000 ms
コード長 1,986 bytes
コンパイル時間 3,181 ms
コンパイル使用メモリ 254,924 KB
実行使用メモリ 96,596 KB
最終ジャッジ日時 2024-09-27 04:48:43
合計ジャッジ時間 32,782 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct S{
	vector<pair<int,int>> vec;

	void init(int l,int r,vector<int> idx,vector<int>&A,int C){
		vec.clear();
		vector<int> cnt(r-l);
		int now=0;
		int R=0;

		for(int i=0;i<idx.size();i++){
			R=max(R,i);

			while(R<idx.size()&&now<r-l){
				cnt[A[idx[R]]-l]++;
				if(cnt[A[idx[R]]-l]==C)now++;
				R++;
			}

			if(now<r-l){
				vec.push_back({idx[i],1e9});
			}else{
				vec.push_back({idx[i],idx[R-1]});
			}

			if(cnt[A[idx[i]]-l]==C){
				now--;
			}
			cnt[A[idx[i]]-l]--;
		}

		vec.push_back({1e9,1e9});
	}

	int query(int l){
		pair<int,int> p={l,0};

		assert(lower_bound(vec.begin(),vec.end(),p)!=vec.end());

		return lower_bound(vec.begin(),vec.end(),p)->second;
	}
};

S dp[3][400009];

int main(){
	int n;cin>>n;
	vector<int> a(n);for(auto&&e:a)cin>>e;

	vector<int> idx(n);for(int i=0;i<n;i++)idx[i]=i;

	auto build=[&](auto build,int l,int r,int p,vector<int> vec)->void {
		for(int i=1;i<=3;i++){
			dp[i-1][p].init(l,r,vec,a,i);
		}

		if(r-l==1)return;

		vector<int> lvec,rvec;

		int m=(l+r)/2;

		for(auto&&e:vec){
			if(a[e]<m){
				lvec.push_back(e);
			}else{
				rvec.push_back(e);
			}
		}

		build(build,l,m,2*p,lvec);
		build(build,m,r,2*p+1,rvec);
	};

	build(build,0,100001,1,idx);

	int q;cin>>q;
    int res_prev=0;

	while(q--){
		int alpha,beta;cin>>alpha>>beta;
		
        int l=res_prev^alpha,r=res_prev^beta;
		
        l--;

		array<int,3> v;

		for(int i=1;i<=3;i++){
			auto search=[&](auto search,int L,int R,int p)->int {
				if(dp[i-1][p].query(l)<r)return R;
				if(R-L==1)return L;

				int m=(L+R)/2;

				int resL=search(search,L,m,2*p);

				if(resL<m)return resL;
				else return search(search,m,R,2*p+1);
			};

			v[i-1]=search(search,0,100001,1);
		}

		int res;

		if(v[2]){
			res=v[0]+v[1]+v[2];
		}else if(v[1]){
			res=v[0]+v[1]+min(0,r-l-v[0]-v[1]-1);
		}else if(v[0]){
			res=v[0]+min(0,r-l-v[0]-2);
		}else{
			res=0;
		}
		cout<<res<<endl;

        res_prev=res;
	}
}
0