oj.uz

Submission #73836

# Submission time Handle Problem Language Result Execution time Memory
73836 2018-08-29T06:18:50 Z zscoder Election (BOI18_election) C++17
28 / 100
 3000 ms 1220 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

string s;
int n;
int del[555555];

int solve(int l, int r)
{
	int cnt=0;
	for(int i=l;i<=r;i++) del[i]=0;
	int ans=0; int S=0; int minpref=0;
	for(int i=l;i<=r;i++)
	{
		S+=(s[i]=='C'?1:-1);
		if(s[i]=='C') cnt++;
		else cnt--;
		if(cnt<0)
		{
			del[i]=1; ans++;
			cnt++;
		}
	}
	minpref=-ans;
	int positive = S - minpref;
	cnt=0; int mx=0;
	for(int i=r;i>=l;i--)
	{
		if(del[i]) 
		{
			cnt = positive; continue;
		}
		if(s[i]=='C') cnt++;
		else cnt--;
		if(cnt<0)
		{
			mx=max(mx,abs(cnt));	
		}
	}
	return ans+mx;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n; cin>>s;
	int q; cin>>q;
	for(int i=0;i<q;i++)
	{
		int l,r; cin>>l>>r; l--; r--;
		cout<<solve(l,r)<<'\n';
	}
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 380 KB Output is correct
2 Correct 11 ms 440 KB Output is correct
3 Correct 11 ms 508 KB Output is correct
4 Correct 11 ms 508 KB Output is correct
5 Correct 7 ms 580 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 380 KB Output is correct
2 Correct 11 ms 440 KB Output is correct
3 Correct 11 ms 508 KB Output is correct
4 Correct 11 ms 508 KB Output is correct
5 Correct 7 ms 580 KB Output is correct
6 Execution timed out 3040 ms 1220 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 380 KB Output is correct
2 Correct 11 ms 440 KB Output is correct
3 Correct 11 ms 508 KB Output is correct
4 Correct 11 ms 508 KB Output is correct
5 Correct 7 ms 580 KB Output is correct
6 Execution timed out 3040 ms 1220 KB Time limit exceeded
7 Halted 0 ms 0 KB -