Submission #87766

#	Time	Username	Problem	Language	Result	Execution time	Memory
87766		memikakizaki	Election (BOI18_election)	C++14	28 / 100	3018 ms	2136 KiB

election

#include <bits/stdc++.h>
using namespace std;
#define long long long
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int N = 5e5+1;

class ElectionsBruteForce {

	int n, q;
	string s;

public:
	void run(istream &cin, ostream &cout) {
		cin >> n >> s >> q;
		for(int i = 0, l, r; i < q; i++) {
			cin >> l >> r;
			--l, --r;
			vector<bool> mark(n);
			int cnt = 0, curr = 0;
			for(int j = l; j <= r; j++) {
				if(curr + (s[j] == 'C' ? 1 : -1) < 0) {
					mark[j] = true;
					++cnt;
				} else curr += (s[j] == 'C' ? 1 : -1);
			}
			curr = 0;
			for(int j = r; j >= l; j--) if(!mark[j]) {
				if(curr + (s[j] == 'C' ? 1 : -1) < 0) mark[j] = true, ++cnt;
				else curr += (s[j] == 'C' ? 1 : -1);
			}
			cout << cnt << '\n';
		}
	}
};


class Solver {
public:
	void solve(std::istream& in, std::ostream& out) {
	    ElectionsBruteForce *obj = new ElectionsBruteForce();
		obj->run(in, out);
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	Solver solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

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