Submission #380569

#	Time	Username	Problem	Language	Result	Execution time	Memory
380569		VodkaInTheJar	Election (BOI18_election)	C++14	28 / 100	3062 ms	1152 KiB

election

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'

using namespace std;

const int maxn = 5e5 + 3; 

int n, q; 
string s;

void read()
{
	cin >> n >> s >> q; 
}

void solve()
{
	while (q--)
	{
		int l, r;
		cin >> l >> r; 
		
		int ans = 0;
		int balance = 0;
		stack <int> st;
		
		
		for (int i = l; i <= r; i++)
		{
			if (s[i-1] == 'C')
			{
				balance++;
				st.push(1);
			}
			
			else 
			{
				if (balance)
				{
					balance--;
					st.push(-1);
				}
				
				else 
				ans++;
			}
		}
		
		int to_add = 0;
		balance = 0; 
		while (!st.empty())
		{
			balance += st.top();
			to_add = max(to_add, -balance);
			st.pop();
		}
		
		cout << ans + to_add << endl; 
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	read();
	solve();
}

• Subtask 1: 28 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18