Submission #64226

#	Time	Username	Problem	Language	Result	Execution time	Memory
64226		jangwonyoung	Election (BOI18_election)	C++14	100 / 100	1434 ms	46344 KiB

election

#include<iostream>
#include<vector>
using namespace std;
const int N=5e5+1,X=1e6+1,TS=1<<20;
#define fi first
#define se second
#define pb push_back
int n,q;
int a[N];
int pre[N];
int nxt[N];
int v[X];
int sum[TS],mi[TS],cnt[TS];
int ans[N];
vector<pair<int,int> >qr[N];
void upd(int id,int l,int r,int pos,int v1,int v2){
	if(l==r){
		sum[id]+=v1;
		mi[id]=min(sum[id],0);
		cnt[id]+=v2;
		return;
	}
	int mid=(l+r)/2;
	if(pos<=mid) upd(id*2,l,mid,pos,v1,v2);
	else upd(id*2+1,mid+1,r,pos,v1,v2);
	sum[id]=sum[id*2]+sum[id*2+1];
	mi[id]=min(mi[id*2+1],mi[id*2]+sum[id*2+1]);
	cnt[id]=cnt[id*2]+cnt[id*2+1];
}
int qr1(int id,int l,int r,int ll,int rr){
	if(l>rr || r<ll) return 0;
	if(ll<=l && r<=rr) return cnt[id];
	int mid=(l+r)/2;
	return qr1(id*2,l,mid,ll,rr)+qr1(id*2+1,mid+1,r,ll,rr);
}
pair<int,int> qr2(int id,int l,int r,int ll,int rr){
	if(l>rr || r<ll) return {0,0};
	if(ll<=l && r<=rr) return {sum[id],mi[id]};
	int mid=(l+r)/2;
	pair<int,int>t1=qr2(id*2,l,mid,ll,rr),t2=qr2(id*2+1,mid+1,r,ll,rr);
	return {t1.fi+t2.fi,min(t2.se,t1.se+t2.fi)};
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for(int i=1; i<=n ;i++){
		char c;
		cin >> c;
		a[i]=(c=='C'?1:-1);
		pre[i]=pre[i-1]+a[i];
		if(v[pre[i]+n]==0 && pre[i]!=0){
			if(pre[i]<0) upd(1,1,n,i,0,1);
			else upd(1,1,n,i,a[i],0);
		}
		else{
			nxt[v[pre[i]+n]]=i;
			upd(1,1,n,i,a[i],0);
		}
		v[pre[i]+n]=i;
	}
	cin >> q;
	for(int i=1; i<=q ;i++){
		int l,r;
		cin >> l >> r;
		qr[l].pb({r,i});
	}
	for(int i=1; i<=n ;i++){
		for(auto cur:qr[i]){
			ans[cur.se]=qr1(1,1,n,i,cur.fi)-qr2(1,1,n,i,cur.fi).se;
		}
		if(a[i]==-1) upd(1,1,n,i,-1,-1);
		else if(nxt[i-1]!=0) upd(1,1,n,nxt[i-1],1,1);
	}
	for(int i=1; i<=q ;i++) cout << ans[i] << '\n';
}

• Subtask 1: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18