Submission #3363652

---

Source Code Expand

#include <bits/stdc++.h>
#define INF 1<<19
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

class segtree{
public:
	static const int N=1<<19;
	int dp[1<<20];
	int cnt[1<<20];
	segtree(){
		for(int i=0;i<N*2;i++){
			dp[i]=INF;
			cnt[i]=0;
		}
	}
	void update(int k,int v){
		k+=N-1;
		dp[k]=v;
		if(v==INF){
			cnt[k]=0;
		}else{
			cnt[k]=1;
		}
		while(k>0){
			k=(k-1)/2;
			dp[k]=min(dp[k*2+1],dp[k*2+2]);
			cnt[k]=cnt[k*2+1]+cnt[k*2+2];
		}
	}

	int query(int a,int b,int k=0,int l=0,int r=N){
		if(b<=l || r<=a)return INF;
		if(a<=l && r<=b)return dp[k];
		int mid=(l+r)/2;
		int vl=query(a,b,k*2+1,l,mid);
		int vr=query(a,b,k*2+2,mid,r);
		return min(vl,vr);
	}

	int query2(int a,int b,int k=0,int l=0,int r=N){
		if(b<=l || r<=a)return 0;
		if(a<=l && r<=b)return cnt[k];
		int mid=(l+r)/2;
		int vl=query2(a,b,k*2+1,l,mid);
		int vr=query2(a,b,k*2+2,mid,r);
		return vl+vr;
	}
};

segtree seg[4];
int bit[300005];

int main(void){
	int q;
	string a,b;
	cin >> q >> a >> b;
	int n=a.size();
	for(int i=0;i<n;i++){
		if(a[i]=='1'){
			bit[i]^=1;
		}
		if(b[i]=='1'){
			bit[i]^=2;
		}
	}
	for(int i=0;i<n;i++){
		seg[bit[i]].update(i,i);
	}
	for(int i=0;i<q;i++){
		char c;
		scanf(" %c",&c);
		if(c=='Q'){
			int pos[4];
			for(int j=0;j<4;j++){
				pos[j]=seg[j].dp[0];
			}
			if(min(pos[1],pos[2])>pos[3]){
				printf("%d\n",n-pos[3]);
			}else if(pos[1]<pos[2]){
				if(seg[0].query(pos[1],n)>seg[3].query(pos[1],n)){
					printf("%d\n",n-pos[1]);
				}else if(seg[2].query(pos[1],n)>seg[3].query(pos[1],n)){
					int v=seg[3].query(pos[1],n);
					printf("%d\n",n-v+seg[1].query2(0,v));
				}else{
					int v=seg[2].query(pos[1],n);
					if(seg[0].query(v,n)==INF){
						printf("%d\n",n-v+seg[1].query2(0,v));
					}else{
						printf("%d\n",n-v+seg[1].query2(0,v)-1);
					}
				}
			}else{
				if(seg[0].query(pos[2],n)==INF || seg[0].query(pos[2],n)>seg[3].query(pos[2],n)){
					printf("%d\n",n-pos[2]);
				}else{
					printf("%d\n",n-pos[2]-1);
				}
			}
		}else{
			int a;
			scanf("%d",&a);
			a=n-a-1;
			seg[bit[a]].update(a,INF);
			if(c=='A'){
				bit[a]^=1;
			}else{
				bit[a]^=2;
			}
			seg[bit[a]].update(a,a);
		}
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:73:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&c);
                  ^
./Main.cpp:104:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&a);
                  ^

Judge Result