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 |
|
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 |