oj.uz

Submission #935788

# Submission time Handle Problem Language Result Execution time Memory
935788 2024-02-29T14:16:45 Z SamNguyen Election (BOI18_election) C++14
28 / 100
 3000 ms 2508 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX = 5e5 + 7;
int N, Q;
char str[MAX];
vector<pair<int, int>> queries;

void input() {
	cin >> N >> (str + 1);
	cin >> Q;
	for (int q = Q; q--; ) {
		int l, r; cin >> l >> r;
		queries.emplace_back(l, r);
	}
}

void solve() {
	for (const auto &query : queries) {
		int l, r;
		tie(l, r) = query;

		set<int> S;
		for (int i = l, sum = 0; i <= r; i++) {
			int new_sum = sum + (str[i] == 'C' ? +1 : -1);
			if (new_sum < 0) 
				S.insert(i);
			else
				sum = new_sum;
		}
		for (int i = r, sum = 0; i >= l; i--) if (S.count(i) == 0) {
			int new_sum = sum + (str[i] == 'C' ? +1 : -1);
			if (new_sum < 0) 
				S.insert(i);
			else
				sum = new_sum;
		}

		cout << S.size() << '\n';
	}
}
	
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	solve();

	return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 348 KB Output is correct
2 Correct 19 ms 524 KB Output is correct
3 Correct 11 ms 600 KB Output is correct
4 Correct 50 ms 532 KB Output is correct
5 Correct 25 ms 344 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 348 KB Output is correct
2 Correct 19 ms 524 KB Output is correct
3 Correct 11 ms 600 KB Output is correct
4 Correct 50 ms 532 KB Output is correct
5 Correct 25 ms 344 KB Output is correct
6 Execution timed out 3020 ms 2508 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 348 KB Output is correct
2 Correct 19 ms 524 KB Output is correct
3 Correct 11 ms 600 KB Output is correct
4 Correct 50 ms 532 KB Output is correct
5 Correct 25 ms 344 KB Output is correct
6 Execution timed out 3020 ms 2508 KB Time limit exceeded
7 Halted 0 ms 0 KB -