oj.uz

Submission #69520

# Submission time Handle Problem Language Result Execution time Memory
69520 2018-08-21T07:17:07 Z khohko Election (BOI18_election) C++17
28 / 100
 3000 ms 49800 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<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())p++,sb.pop();
			if(sb.size()){
				sb.pop();
				sa.pop();
				p++;
			}
		}
		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 51 ms 47352 KB Output is correct
2 Correct 52 ms 47592 KB Output is correct
3 Correct 47 ms 47592 KB Output is correct
4 Correct 56 ms 47592 KB Output is correct
5 Correct 50 ms 47660 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 47352 KB Output is correct
2 Correct 52 ms 47592 KB Output is correct
3 Correct 47 ms 47592 KB Output is correct
4 Correct 56 ms 47592 KB Output is correct
5 Correct 50 ms 47660 KB Output is correct
6 Execution timed out 3050 ms 49800 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 47352 KB Output is correct
2 Correct 52 ms 47592 KB Output is correct
3 Correct 47 ms 47592 KB Output is correct
4 Correct 56 ms 47592 KB Output is correct
5 Correct 50 ms 47660 KB Output is correct
6 Execution timed out 3050 ms 49800 KB Time limit exceeded
7 Halted 0 ms 0 KB -