Submission #3782058


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);
	z=merge(lc[z],rc[z]);
	x=merge(x,z);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();
			if(B.size()){
				iter=--B.end();
				rank(*iter);Iter=A.find(*iter);
				if(Iter==A.end()){
					Iter=A.lower_bound(*iter);
					if(Iter!=A.begin()&&a[*--Iter])--ans;
				}
			}
			cout<<ans<<endl;
		}
		if(opt=='A'){
			iter=A.find(x);a[x]^=1;
			if(iter==A.end())A.insert(x),insert(x);
			else A.erase(x),Delete(x);
		}
		if(opt=='B'){
			iter=A.find(x);b[x]^=1;
			if(iter==A.end())A.insert(x),insert(x);
			else A.erase(x),Delete(x);
			if(iter==B.end())B.insert(x);
			else B.erase(x);
		}
	}
	return 0;
}

Submission Info

Submission Time
Task I - A + B
User the_Despair_
Language C++ (GCC 5.4.1)
Score 0
Code Size 1859 Byte
Status WA
Exec Time 692 ms
Memory 41500 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 7
WA × 59
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 WA 5 ms 12544 KB
00-gray1-2.txt WA 5 ms 12544 KB
00-gray1-3.txt WA 5 ms 12544 KB
00-gray1-4.txt WA 5 ms 12544 KB
00-gray1-5.txt WA 5 ms 12544 KB
00-gray1-6.txt WA 5 ms 12544 KB
00-gray1-7.txt WA 5 ms 12544 KB
00-gray2-1.txt WA 5 ms 12544 KB
00-gray2-2.txt WA 5 ms 12544 KB
00-gray2-3.txt WA 5 ms 12544 KB
00-gray2-4.txt WA 5 ms 12544 KB
00-gray2-5.txt WA 5 ms 12544 KB
00-gray2-6.txt WA 5 ms 12544 KB
00-gray2-7.txt WA 6 ms 12544 KB
00-gray3-1.txt WA 5 ms 12544 KB
00-gray3-2.txt WA 5 ms 12544 KB
00-gray3-3.txt WA 5 ms 12544 KB
00-gray3-4.txt WA 5 ms 12544 KB
00-gray3-5.txt WA 5 ms 12544 KB
00-gray3-6.txt WA 6 ms 12544 KB
00-gray3-7.txt WA 7 ms 12544 KB
00-gray4-1.txt WA 5 ms 12544 KB
00-gray4-2.txt WA 5 ms 12544 KB
00-gray4-3.txt WA 5 ms 12544 KB
00-gray4-4.txt WA 5 ms 12544 KB
00-gray4-5.txt WA 6 ms 12544 KB
00-gray4-6.txt WA 7 ms 12544 KB
00-gray4-7.txt WA 9 ms 12544 KB
00-gray5-1.txt WA 5 ms 12544 KB
00-gray5-2.txt WA 5 ms 12544 KB
00-gray5-3.txt WA 5 ms 12544 KB
00-gray5-4.txt WA 6 ms 12544 KB
00-gray5-5.txt WA 6 ms 12544 KB
00-gray5-6.txt WA 8 ms 12544 KB
00-gray5-7.txt WA 13 ms 12544 KB
00-gray6-1.txt WA 5 ms 12544 KB
00-gray6-2.txt WA 5 ms 12544 KB
00-gray6-3.txt WA 6 ms 12544 KB
00-gray6-4.txt WA 6 ms 12544 KB
00-gray6-5.txt WA 8 ms 12544 KB
00-gray6-6.txt WA 12 ms 12544 KB
00-gray6-7.txt WA 20 ms 12544 KB
00-gray7-1.txt WA 5 ms 12544 KB
00-gray7-2.txt WA 5 ms 12544 KB
00-gray7-3.txt WA 6 ms 12544 KB
00-gray7-4.txt WA 8 ms 12544 KB
00-gray7-5.txt WA 12 ms 12544 KB
00-gray7-6.txt WA 20 ms 12544 KB
00-gray7-7.txt WA 35 ms 12672 KB
00-sample1.txt AC 5 ms 12544 KB
50-random00.txt WA 341 ms 15488 KB
50-random01.txt WA 324 ms 15488 KB
50-random02.txt WA 332 ms 15488 KB
50-random03.txt WA 324 ms 15488 KB
50-random04.txt WA 323 ms 15488 KB
50-random05.txt WA 671 ms 37664 KB
50-random06.txt WA 654 ms 36884 KB
50-random07.txt AC 677 ms 38420 KB
50-random08.txt AC 652 ms 36756 KB
50-random09.txt AC 692 ms 41236 KB
50-random10.txt AC 147 ms 19536 KB
50-random11.txt AC 144 ms 19536 KB
50-random12.txt AC 141 ms 19536 KB
vsparallel00.txt WA 662 ms 41500 KB
vsparallel01.txt WA 676 ms 41500 KB
vsparallel02.txt WA 639 ms 41500 KB