Submission #73827

#	Time	Username	Problem	Language	Result	Execution time	Memory
73827		zscoder	Election (BOI18_election)	C++17	28 / 100	3099 ms	1616 KiB

election

#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 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18