Submission #956556

#	Time	Username	Problem	Language	Result	Execution time	Memory
956556		moonrabbit2	Election (BOI18_election)	C++17	100 / 100	541 ms	54076 KiB

election

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using pii=array<int,2>;
using tii=array<int,3>;
const int N=500005;
int n,a[N],s[N],q,ans[N],pos[2*N];
vector<pii> qry[N];
string S;
struct ST{
	tii T[2*N];
	tii mrg(tii L,tii R){
		return tii{min(L[0]+R[1],R[0]),L[1]+R[1],L[2]+R[2]};
	}
	void init(int nd,int l,int r){
		T[nd]={0,0,r-l+1};
		if(l==r) return;
		int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
		init(ln,l,m); init(rn,m+1,r);
	}
	void upd(int nd,int l,int r,int x,int v){
		if(l==r){
			T[nd]={min(0,v),v,v==0};
			return;
		}
		int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
		if(x<=m) upd(ln,l,m,x,v);
		else upd(rn,m+1,r,x,v);
		T[nd]=mrg(T[ln],T[rn]);
	}
	tii qry(int nd,int l,int r,int s,int e){
		if(s<=l&&r<=e) return T[nd];
		int m=(l+r)>>1,ln=nd+1,rn=nd+2*(m-l+1);
		if(e<=m) return qry(ln,l,m,s,e);
		if(m+1<=s) return qry(rn,m+1,r,s,e);
		return mrg(qry(ln,l,m,s,e),qry(rn,m+1,r,s,e));
	}
}T;
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>S>>q;
	for(int i=1;i<=n;i++){
		if(S[i-1]=='C') a[i]=1;
		else a[i]=-1;
		s[i]=s[i-1]+a[i];
	}
	for(int l,r,i=1;i<=q;i++){
		cin>>l>>r;
		qry[l].push_back({i,r});
	}
	T.init(1,1,n);
	for(int i=n;i>=1;i--){
		if(pos[s[i]+n]) T.upd(1,1,n,pos[s[i]+n],a[pos[s[i]+n]]);
		pos[s[i]+n]=i;
		if(a[i]>0){
			T.upd(1,1,n,i,a[i]);
			if(pos[s[i]-1+n]) T.upd(1,1,n,pos[s[i]-1+n],a[pos[s[i]-1+n]]);			
		}
		for(auto [idx,j]: qry[i]){
			tii Q=T.qry(1,1,n,i,j);
			ans[idx]=-Q[0]+Q[2];
		}
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
	/*
		int s=0,ans=0,mn=0;
		for(int i=l;i<=r;i++){
			s+=a[i];
			if(s<mn){
				chk[i]=1;
				mn=s;
				ans++;
			} else{
				chk[i]=0;
			}
		}
		s=mn=0;
		for(int i=r;i>=l;i--) if(!chk[i]){
			s+=a[i];
			mn=min(mn,s);
		}
		ans-=mn;
		cout<<ans<<"\n";
	}*/
	return 0;
}

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