結果

問題 No.2935 Division Into 3 (Mex Edition)
ユーザー nouka28nouka28
提出日時 2024-10-04 00:03:31
言語 C++23
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 87 ms
40,540 KB
testcase_01 AC 90 ms
40,544 KB
testcase_02 AC 90 ms
40,544 KB
testcase_03 AC 417 ms
51,056 KB
testcase_04 AC 593 ms
57,568 KB
testcase_05 AC 611 ms
58,272 KB
testcase_06 AC 644 ms
58,380 KB
testcase_07 AC 483 ms
53,932 KB
testcase_08 AC 494 ms
55,232 KB
testcase_09 AC 519 ms
58,152 KB
testcase_10 AC 555 ms
57,860 KB
testcase_11 AC 363 ms
57,956 KB
testcase_12 AC 433 ms
50,480 KB
testcase_13 AC 512 ms
46,960 KB
testcase_14 AC 511 ms
57,636 KB
testcase_15 AC 517 ms
50,892 KB
testcase_16 AC 399 ms
48,120 KB
testcase_17 AC 575 ms
56,084 KB
testcase_18 AC 579 ms
56,088 KB
testcase_19 AC 435 ms
48,000 KB
testcase_20 AC 494 ms
49,772 KB
testcase_21 AC 353 ms
48,848 KB
testcase_22 AC 488 ms
49,780 KB
testcase_23 AC 523 ms
49,776 KB
権限があれば一括ダウンロードができます

ソースコード

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