Submission #709731

#	Time	Username	Problem	Language	Result	Execution time	Memory
709731		surgutti	Election (BOI18_election)	C++14	100 / 100	346 ms	20648 KiB

election

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);

	int n; string s;
	cin >> n >> s;

	struct Node {
		int ans, sum, pre, suf;
	
		Node operator+ (Node other) {
			other.ans = min({ans + other.sum, sum + other.ans, pre + other.suf});
			other.pre = min(pre, sum + other.pre);
			other.suf = min(suf + other.sum, other.suf);
			other.sum = sum + other.sum;

			return other;
		}
	};

	int tree_size = 1;
	while (tree_size < n)
		tree_size <<= 1;

	vector<Node> tree(tree_size << 1);

	for (int i = 0; i < n; i++) {
		if (s[i] == 'C')
			tree[i + tree_size] = Node{0, +1, 0, 0};
		else
		if (s[i] == 'T')
			tree[i + tree_size] = Node{-1, -1, -1, -1};
	}

	for (int i = tree_size - 1; i; i--)
		tree[i] = tree[i << 1 | 0] + tree[i << 1 | 1];

	int q; cin >> q;
	while (q--) {
		int l, r; cin >> l >> r;

		Node L{0, 0, 0, 0}, R{0, 0, 0, 0};
		for (l += tree_size - 1, r += tree_size; l < r; l >>= 1, r >>= 1) {
			if (l & 1)
				L = L + tree[l++];
			if (r & 1)
				R = tree[--r] + R;
		}

		cout << - (L + R).ans << '\n';
	}

}

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