제출 #935788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
935788		SamNguyen	Election (BOI18_election)	C++14	28 / 100	3020 ms	2508 KiB

election

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