結果

問題 No.2935 Division Into 3 (Mex Edition)
ユーザー nouka28
提出日時 2024-10-04 00:03:31
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 644 ms / 5,000 ms
コード長 1,757 bytes
コンパイル時間 3,498 ms
コンパイル使用メモリ 253,792 KB
実行使用メモリ 58,380 KB
最終ジャッジ日時 2024-10-04 00:03:51
合計ジャッジ時間 17,259 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

vector<pair<int,int>> dp[3][400009];

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

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

	vector<int> P;for(int i=0;i<n;i++)P.push_back(i);

	auto build=[&](auto build,int l,int r,int k,vector<int>&idx)->void {
		for(int C=1;C<=3;C++){
			int R=0,now=0;
			vector<int> cnt(r-l);

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

				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){
					dp[C-1][k].push_back({idx[i],idx[R-1]});
				}

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

				cnt[a[idx[i]]-l]--;
			}

			dp[C-1][k].push_back({1e9,1e9});
		}

		if(r-l==1)return;

		vector<int> idxL,idxR;
		int mid=(l+r)/2;

		for(auto&&e:idx){
			if(a[e]<mid)idxL.push_back(e);
			else idxR.push_back(e);
		}

		build(build,l,mid,2*k+1,idxL);
		build(build,mid,r,2*k+2,idxR);
	};

	build(build,0,100001,0,P);

	int q;cin>>q;

	int res_prev=0;

	while(q--){
		int x,y;cin>>x>>y;

		int L=x^res_prev,R=y^res_prev;

		// cout<<"L R : "<<L<<" "<<R<<endl;

		L--;

		assert(0<=L&&R-L>=2&&R<=n);

		auto search=[&](auto search,int l,int r,int k,int C)->int {
			pair<int,int> p={L,0};

			auto it=lower_bound(dp[C-1][k].begin(),dp[C-1][k].end(),p);

			if(it->second<R){
				return r;
			}

			if(r-l==1){
				return l;
			}

			int mid=(l+r)/2;

			int res=search(search,l,mid,2*k+1,C);

			if(res<mid)return res;
			else return search(search,mid,r,2*k+2,C);
		};

		array<int,3> v;

		for(int C=1;C<=3;C++){
			v[C-1]=search(search,0,100001,0,C);
		}

		int res=min(v[0]+v[1]+v[2],R-L-(!v[0])-(!v[1])-(!v[2]));

		cout<<res<<endl;

		res_prev=res;
	}
}
0