oj.uz

Submission #69525

# Submission time Handle Problem Language Result Execution time Memory
69525 2018-08-21T07:43:41 Z khohko Election (BOI18_election) C++17
28 / 100
 3000 ms 49952 KB 
#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<pair<ll,ll> > sa;
		queue<pair<ll,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,1});
			}
		}
		//cout<<endl;
		for(ll i=r; i>=l; i--){
			if(-sum(i,r)>mb){
				mb++;
				sb.push({i,1});
			//	cout<<i<<endl;
			}
		}

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


}

Compilation message

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
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 47352 KB Output is correct
2 Correct 54 ms 47532 KB Output is correct
3 Correct 46 ms 47552 KB Output is correct
4 Correct 56 ms 47756 KB Output is correct
5 Correct 50 ms 47756 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 47352 KB Output is correct
2 Correct 54 ms 47532 KB Output is correct
3 Correct 46 ms 47552 KB Output is correct
4 Correct 56 ms 47756 KB Output is correct
5 Correct 50 ms 47756 KB Output is correct
6 Execution timed out 3042 ms 49952 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 47352 KB Output is correct
2 Correct 54 ms 47532 KB Output is correct
3 Correct 46 ms 47552 KB Output is correct
4 Correct 56 ms 47756 KB Output is correct
5 Correct 50 ms 47756 KB Output is correct
6 Execution timed out 3042 ms 49952 KB Time limit exceeded
7 Halted 0 ms 0 KB -