Submission #69563

#	Time	Username	Problem	Language	Result	Execution time	Memory
69563		khohko	Election (BOI18_election)	C++17	100 / 100	2789 ms	148928 KiB

election

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define MAX ((ll)(1e9+100))
#define MX ((ll)(1e6+100))
#define ARRS ((ll)(2e6+100))
#define HS ((ll)(233))
#define MOD ((ll)(1e9+7))
#define EP ((double)(1e-9))
#define LG 21
#define mul(a,b) a=((a)*(b))%MOD
using namespace std;

ll n;
ll m,k;
vector<ll> v[ARRS];
ll f[ARRS];
ll a[ARRS];
ll sm[ARRS];
ll ct[ARRS];

ll sum(ll l,ll r){
	return sm[r]-sm[l-1];
}

struct node{
	node *L,*R;
	ll u,d,s,sm;
	node(){
		L=R=NULL;
		u=0;
		d=0;
		s=0;
		sm=0;
	}
	void updt(){
		node a=*L;
		node b=*R;
		sm=a.sm+b.sm;
		///////
		u=max(a.u,b.u+a.sm);
		d=max(b.d,a.d+b.sm);

		b.u=max(0ll,a.sm+b.u-a.u);
		a.d=max(0ll,b.sm+a.d-b.d);

		s=min(b.s,b.u)+
			min(a.s,a.d)+
			max(0ll,min(b.u-b.s,a.d-a.s));
	}
};

node join(node a,node b){
	node x;
	x.sm=a.sm+b.sm;
///////
	x.u=max(a.u,b.u+a.sm);
	x.d=max(b.d,a.d+b.sm);

	b.u=max(0ll,a.sm+b.u-a.u);
	a.d=max(0ll,b.sm+a.d-b.d);
	x.s=min(b.s,b.u)+
			min(a.s,a.d)+
				max(0ll,min(b.u-b.s,a.d-a.s));



	return x;
}

void init(ll l,ll r,node *& x){
	if(!x)x=new node();
	if(l==r-1){
		if(a[l]==1){
			x->u=0;
			x->d=0;
			x->s=0;
			x->sm=-1;
		}
		else {
			x->u=1;
			x->d=1;
			x->s=1;
			x->sm=1;
		}
		return;
	}
	init(l,l+r>>1,x->L);
	init(l+r>>1,r,x->R);
	x->updt();
//	cout<<l<<" "<<r<<" "<<x->u<<" "<<x->d<<" "<<x->s<<" "<<x->sm<<endl;
}
node pas;
ll wl,wr;
void quer(ll l,ll r,node *& x){
	if(wr<l||r-1<wl)return;
	if(wl<=l&&r-1<=wr){
		pas=join(pas,*x);
		return;
	}
	quer(l,l+r>>1,x->L);
	quer(l+r>>1,r,x->R);
}

node *rt=NULL;
int main(){
	#ifdef KHOKHO
		freopen("in.in","r",stdin);
		freopen("out.out","w",stdout);
	#endif // KHOKHO
	ios::sync_with_stdio(0);
	ll n;
	string s;
	cin>>n>>s;
	for(int i=1; i<=n; i++){
		if(s[i-1]=='C')a[i]=1;
		else a[i]=-1;
	}

	ll q,l,r;
	init(1,n+1,rt);
	cin>>q;
	while(q--){
		cin>>wl>>wr;
		pas=*(new node());
		quer(1,n+1,rt);
		cout<<pas.u+pas.d-pas.s<<endl;
	}
}

Compilation message (stderr)

election.cpp: In function 'void init(long long int, long long int, node*&)':
election.cpp:92:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  init(l,l+r>>1,x->L);
         ~^~
election.cpp:93:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  init(l+r>>1,r,x->R);
       ~^~
election.cpp: In function 'void quer(long long int, long long int, node*&)':
election.cpp:105:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  quer(l,l+r>>1,x->L);
         ~^~
election.cpp:106:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  quer(l+r>>1,r,x->R);
       ~^~
election.cpp: In function 'int main()':
election.cpp:124:7: warning: unused variable 'l' [-Wunused-variable]
  ll q,l,r;
       ^
election.cpp:124:9: warning: unused variable 'r' [-Wunused-variable]
  ll q,l,r;
         ^

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