oj.uz

Submission #73827

# Submission time Handle Problem Language Result Execution time Memory
73827 2018-08-29T05:37:14 Z zscoder Election (BOI18_election) C++17
28 / 100
 3000 ms 1616 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;
	for(int i=l;i<=r;i++)
	{
		if(s[i]=='C') cnt++;
		else cnt--;
		if(cnt<0)
		{
			del[i]=1; ans++;
			cnt++;
		}
	}
	cnt=0;
	for(int i=r;i>=l;i--)
	{
		if(del[i]) continue;
		if(s[i]=='C') cnt++;
		else cnt--;
		if(cnt<0)
		{
			del[i]=1; ans++; cnt++;
		}
	}
	return ans;
}

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 14 ms 380 KB Output is correct
2 Correct 13 ms 532 KB Output is correct
3 Correct 12 ms 592 KB Output is correct
4 Correct 12 ms 612 KB Output is correct
5 Correct 8 ms 764 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 380 KB Output is correct
2 Correct 13 ms 532 KB Output is correct
3 Correct 12 ms 592 KB Output is correct
4 Correct 12 ms 612 KB Output is correct
5 Correct 8 ms 764 KB Output is correct
6 Execution timed out 3099 ms 1616 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 380 KB Output is correct
2 Correct 13 ms 532 KB Output is correct
3 Correct 12 ms 592 KB Output is correct
4 Correct 12 ms 612 KB Output is correct
5 Correct 8 ms 764 KB Output is correct
6 Execution timed out 3099 ms 1616 KB Time limit exceeded
7 Halted 0 ms 0 KB -