Submission #3782351


Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int _=1e6+20;
int a[_],b[_],lc[_],rc[_],siz[_],w[_],key[_],rt,n,cnt,ans;
set<int>A,B;set<int>::iterator iter,Iter; string aa,bb;
void pushup(int x){siz[x]=siz[lc[x]]+siz[rc[x]]+1;}
void split(const int no,int &x,int &y,const int val){
	if(!no){x=y=0;return;}
	if(w[no]<=val)x=no,split(rc[x],rc[x],y,val);
	else y=no,split(lc[y],x,lc[y],val);
	pushup(no);
}
int merge(const int x,const int y){
	if(!x||!y)return x+y;
	if(key[x]>key[y])return rc[x]=merge(rc[x],y),pushup(x),x;
	else return lc[y]=merge(x,lc[y]),pushup(y),y;
}
void insert(int val){
	int x,y;split(rt,x,y,val);
	w[++cnt]=val;key[cnt]=rand();siz[cnt]=1;
	x=merge(x,cnt);rt=merge(x,y);
}
void Delete(int val){
	int x,y,z;
	split(rt,x,y,val);
	split(x,x,z,val-1);
	rt=merge(x,y);
}
void rank(int val){
	int x,y;
	split(rt,x,y,val);
	ans+=siz[x];rt=merge(x,y);
}
int main(){
	ios::sync_with_stdio(false);
	int Q;cin>>Q>>aa>>bb;srand(time(0));
	for(int i=0,l=aa.length();i<l;++i)
		a[l-i]=aa[i]-'0';
	for(int i=0,l=bb.length();i<l;++i)
		b[l-i]=bb[i]-'0';
	n=max(aa.length(),bb.length());
	for(int i=1;i<=n;++i){
		a[i]^=1;
		if(a[i]!=b[i])A.insert(i),insert(i);
		if(b[i])B.insert(i);
	}
	while(Q--){
		char opt ;int x;cin>>opt;
		if(opt=='A'||opt=='B')cin>>x,++x;
		if(opt=='Q'){
			ans=n-A.size();
			iter=--B.end();rank(*iter);
			Iter=A.find(*iter);
			if(Iter==A.end()){
				Iter=A.lower_bound(*iter);
				if(Iter==A.begin()||!b[*--Iter])--ans;
			}
			cout<<ans<<endl;
		}
		if(opt=='A'){
			a[x]^=1;
			if(a[x]!=b[x])A.insert(x),insert(x);
			else A.erase(A.find(x)),Delete(x);
		}
		if(opt=='B'){
			b[x]^=1;
			if(a[x]!=b[x])A.insert(x),insert(x);
			else A.erase(A.find(x)),Delete(x);
			if(b[x])B.insert(x);
			else B.erase(B.find(x));
		}
	}
	return 0;
}

Submission Info

Submission Time
Task I - A + B
User the_Despair_
Language C++ (GCC 5.4.1)
Score 100
Code Size 1777 Byte
Status AC
Exec Time 729 ms
Memory 41500 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 66
Set Name Test Cases
All 00-gray1-1.txt, 00-gray1-2.txt, 00-gray1-3.txt, 00-gray1-4.txt, 00-gray1-5.txt, 00-gray1-6.txt, 00-gray1-7.txt, 00-gray2-1.txt, 00-gray2-2.txt, 00-gray2-3.txt, 00-gray2-4.txt, 00-gray2-5.txt, 00-gray2-6.txt, 00-gray2-7.txt, 00-gray3-1.txt, 00-gray3-2.txt, 00-gray3-3.txt, 00-gray3-4.txt, 00-gray3-5.txt, 00-gray3-6.txt, 00-gray3-7.txt, 00-gray4-1.txt, 00-gray4-2.txt, 00-gray4-3.txt, 00-gray4-4.txt, 00-gray4-5.txt, 00-gray4-6.txt, 00-gray4-7.txt, 00-gray5-1.txt, 00-gray5-2.txt, 00-gray5-3.txt, 00-gray5-4.txt, 00-gray5-5.txt, 00-gray5-6.txt, 00-gray5-7.txt, 00-gray6-1.txt, 00-gray6-2.txt, 00-gray6-3.txt, 00-gray6-4.txt, 00-gray6-5.txt, 00-gray6-6.txt, 00-gray6-7.txt, 00-gray7-1.txt, 00-gray7-2.txt, 00-gray7-3.txt, 00-gray7-4.txt, 00-gray7-5.txt, 00-gray7-6.txt, 00-gray7-7.txt, 00-sample1.txt, 50-random00.txt, 50-random01.txt, 50-random02.txt, 50-random03.txt, 50-random04.txt, 50-random05.txt, 50-random06.txt, 50-random07.txt, 50-random08.txt, 50-random09.txt, 50-random10.txt, 50-random11.txt, 50-random12.txt, vsparallel00.txt, vsparallel01.txt, vsparallel02.txt
Case Name Status Exec Time Memory
00-gray1-1.txt AC 4 ms 12544 KB
00-gray1-2.txt AC 4 ms 12544 KB
00-gray1-3.txt AC 4 ms 12544 KB
00-gray1-4.txt AC 4 ms 12544 KB
00-gray1-5.txt AC 4 ms 12544 KB
00-gray1-6.txt AC 5 ms 12544 KB
00-gray1-7.txt AC 5 ms 12544 KB
00-gray2-1.txt AC 4 ms 12544 KB
00-gray2-2.txt AC 4 ms 12544 KB
00-gray2-3.txt AC 4 ms 12544 KB
00-gray2-4.txt AC 4 ms 12544 KB
00-gray2-5.txt AC 5 ms 12544 KB
00-gray2-6.txt AC 5 ms 12544 KB
00-gray2-7.txt AC 6 ms 12544 KB
00-gray3-1.txt AC 4 ms 12544 KB
00-gray3-2.txt AC 4 ms 12544 KB
00-gray3-3.txt AC 4 ms 12544 KB
00-gray3-4.txt AC 5 ms 12544 KB
00-gray3-5.txt AC 5 ms 12544 KB
00-gray3-6.txt AC 5 ms 12544 KB
00-gray3-7.txt AC 7 ms 12544 KB
00-gray4-1.txt AC 4 ms 12544 KB
00-gray4-2.txt AC 4 ms 12544 KB
00-gray4-3.txt AC 5 ms 12544 KB
00-gray4-4.txt AC 5 ms 12544 KB
00-gray4-5.txt AC 5 ms 12544 KB
00-gray4-6.txt AC 6 ms 12544 KB
00-gray4-7.txt AC 8 ms 12544 KB
00-gray5-1.txt AC 4 ms 12544 KB
00-gray5-2.txt AC 4 ms 12544 KB
00-gray5-3.txt AC 5 ms 12544 KB
00-gray5-4.txt AC 5 ms 12544 KB
00-gray5-5.txt AC 6 ms 12544 KB
00-gray5-6.txt AC 8 ms 12544 KB
00-gray5-7.txt AC 12 ms 12544 KB
00-gray6-1.txt AC 4 ms 12544 KB
00-gray6-2.txt AC 5 ms 12544 KB
00-gray6-3.txt AC 5 ms 12544 KB
00-gray6-4.txt AC 6 ms 12544 KB
00-gray6-5.txt AC 8 ms 12544 KB
00-gray6-6.txt AC 12 ms 12544 KB
00-gray6-7.txt AC 21 ms 12544 KB
00-gray7-1.txt AC 5 ms 12544 KB
00-gray7-2.txt AC 5 ms 12544 KB
00-gray7-3.txt AC 6 ms 12544 KB
00-gray7-4.txt AC 8 ms 12544 KB
00-gray7-5.txt AC 12 ms 12544 KB
00-gray7-6.txt AC 20 ms 12544 KB
00-gray7-7.txt AC 36 ms 12672 KB
00-sample1.txt AC 4 ms 12544 KB
50-random00.txt AC 346 ms 15488 KB
50-random01.txt AC 345 ms 15488 KB
50-random02.txt AC 340 ms 15488 KB
50-random03.txt AC 345 ms 15488 KB
50-random04.txt AC 342 ms 15488 KB
50-random05.txt AC 658 ms 37664 KB
50-random06.txt AC 631 ms 37012 KB
50-random07.txt AC 640 ms 38420 KB
50-random08.txt AC 635 ms 36756 KB
50-random09.txt AC 684 ms 41236 KB
50-random10.txt AC 129 ms 19536 KB
50-random11.txt AC 129 ms 19536 KB
50-random12.txt AC 130 ms 19536 KB
vsparallel00.txt AC 708 ms 41500 KB
vsparallel01.txt AC 729 ms 41500 KB
vsparallel02.txt AC 689 ms 41500 KB