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