oj.uz

Submission #709731

# Submission time Handle Problem Language Result Execution time Memory
709731 2023-03-14T09:39:18 Z surgutti Election (BOI18_election) C++14
100 / 100
 346 ms 20648 KB 
#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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 324 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 324 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 32 ms 4936 KB Output is correct
7 Correct 30 ms 5328 KB Output is correct
8 Correct 29 ms 5172 KB Output is correct
9 Correct 28 ms 5268 KB Output is correct
10 Correct 31 ms 5164 KB Output is correct
11 Correct 33 ms 5324 KB Output is correct
12 Correct 31 ms 5400 KB Output is correct
13 Correct 32 ms 5324 KB Output is correct
14 Correct 32 ms 5312 KB Output is correct
15 Correct 32 ms 5344 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 324 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 32 ms 4936 KB Output is correct
7 Correct 30 ms 5328 KB Output is correct
8 Correct 29 ms 5172 KB Output is correct
9 Correct 28 ms 5268 KB Output is correct
10 Correct 31 ms 5164 KB Output is correct
11 Correct 33 ms 5324 KB Output is correct
12 Correct 31 ms 5400 KB Output is correct
13 Correct 32 ms 5324 KB Output is correct
14 Correct 32 ms 5312 KB Output is correct
15 Correct 32 ms 5344 KB Output is correct
16 Correct 258 ms 19784 KB Output is correct
17 Correct 257 ms 19812 KB Output is correct
18 Correct 269 ms 19772 KB Output is correct
19 Correct 209 ms 19296 KB Output is correct
20 Correct 286 ms 18768 KB Output is correct
21 Correct 274 ms 20560 KB Output is correct
22 Correct 278 ms 20408 KB Output is correct
23 Correct 296 ms 20648 KB Output is correct
24 Correct 267 ms 20364 KB Output is correct
25 Correct 346 ms 19952 KB Output is correct