oj.uz

Submission #380569

# Submission time Handle Problem Language Result Execution time Memory
380569 2021-03-22T11:12:53 Z VodkaInTheJar Election (BOI18_election) C++14
28 / 100
 3000 ms 1152 KB 
#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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 364 KB Output is correct
2 Correct 6 ms 364 KB Output is correct
3 Correct 6 ms 364 KB Output is correct
4 Correct 5 ms 364 KB Output is correct
5 Correct 4 ms 364 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 364 KB Output is correct
2 Correct 6 ms 364 KB Output is correct
3 Correct 6 ms 364 KB Output is correct
4 Correct 5 ms 364 KB Output is correct
5 Correct 4 ms 364 KB Output is correct
6 Execution timed out 3062 ms 1152 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 364 KB Output is correct
2 Correct 6 ms 364 KB Output is correct
3 Correct 6 ms 364 KB Output is correct
4 Correct 5 ms 364 KB Output is correct
5 Correct 4 ms 364 KB Output is correct
6 Execution timed out 3062 ms 1152 KB Time limit exceeded
7 Halted 0 ms 0 KB -