Submission #69519

#	Time	Username	Problem	Language	Result	Execution time	Memory
69519		khohko	Election (BOI18_election)	C++17	0 / 100	48 ms	47356 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];
}

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;
	}
	for(int i=1; i<=n; i++)
		sm[i]=sm[i-1]+a[i];
	for(int i=1; i<=n; i++)
		ct[i]=ct[i-1]+(a[i]==-1);
	ll q,l,r;
	cin>>q;
	while(q--){
		cin>>l>>r;
		ll mx=l;
		ll mn=r;
		ll ma=0,mb=0;
		stack<ll> sa;
		queue<ll> sb;
	//	cout<<"------"<<endl;
		for(ll i=l; i<=r; i++){
			//cout<<l<<" "<<i<<" "<<-sum(l,i)<<endl;
			if(-sum(l,i)>ma){
				ma++;
				sa.push(i);
				//cout<<i<<endl;
			}
		}
		//cout<<endl;
		for(ll i=r; i>=l; i--){
			if(-sum(i,r)>mb){
				mb++;
				sb.push(i);
			//	cout<<i<<endl;
			}
		}

		ll p=0;
		while(sa.size()&&sb.size()){
			while(sb.size()&&sb.front()>sa.top())sb.pop();
			if(sb.size()){
				sb.pop();
				sa.pop();
				p++;
			}
		}
		cout<<p+sa.size()+sb.size()<<endl;
	}


}

Compilation message (stderr)

election.cpp: In function 'int main()':
election.cpp:51:6: warning: unused variable 'mx' [-Wunused-variable]
   ll mx=l;
      ^~
election.cpp:52:6: warning: unused variable 'mn' [-Wunused-variable]
   ll mn=r;
      ^~

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