oj.uz

Submission #376635

# Submission time Handle Problem Language Result Execution time Memory
376635 2021-03-11T21:40:52 Z couplefire Election (BOI18_election) C++17
100 / 100
 673 ms 27884 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Node {
	int l_max, r_max, tot, ans;

	Node operator+(Node b) {
		Node ret;
		ret.l_max = max(l_max, b.l_max + tot);
		ret.r_max = max(r_max + b.tot, b.r_max);
		ret.tot = tot + b.tot;
		ret.ans = max(max(ans + b.tot, b.ans + tot), l_max + b.r_max);
		return ret;
	}
};

Node segtree[2000001];
char s[500001];
int n;

void build(int node = 1, int l = 1, int r = n) {
	if (l == r) {
		if (s[l] == 'T') segtree[node] = {1, 1, 1, 1};
		else segtree[node] = {0, 0, -1, 0};
	} else {
		int mid = (l + r) / 2;
		build(node * 2, l, mid);
		build(node * 2 + 1, mid + 1, r);
		segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
	}
}

Node query(int a, int b, int node = 1, int l = 1, int r = n) {
	if (l > b || r < a) return {0, 0, 0, 0};
	if (l >= a && r <= b) return segtree[node];
	int mid = (l + r) / 2;
	return query(a, b, node * 2, l, mid) + query(a, b, node * 2 + 1, mid + 1, r);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	FOR(i, 1, n + 1) cin >> s[i];
	build();
	int q;
	cin >> q;
	while (q--) {
		int a, b;
		cin >> a >> b;
		cout << query(a, b).ans << '\n';
	}
	return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 67 ms 5740 KB Output is correct
7 Correct 58 ms 5740 KB Output is correct
8 Correct 62 ms 5740 KB Output is correct
9 Correct 54 ms 5740 KB Output is correct
10 Correct 63 ms 5612 KB Output is correct
11 Correct 64 ms 5868 KB Output is correct
12 Correct 66 ms 5868 KB Output is correct
13 Correct 64 ms 5868 KB Output is correct
14 Correct 67 ms 5888 KB Output is correct
15 Correct 65 ms 5740 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 67 ms 5740 KB Output is correct
7 Correct 58 ms 5740 KB Output is correct
8 Correct 62 ms 5740 KB Output is correct
9 Correct 54 ms 5740 KB Output is correct
10 Correct 63 ms 5612 KB Output is correct
11 Correct 64 ms 5868 KB Output is correct
12 Correct 66 ms 5868 KB Output is correct
13 Correct 64 ms 5868 KB Output is correct
14 Correct 67 ms 5888 KB Output is correct
15 Correct 65 ms 5740 KB Output is correct
16 Correct 652 ms 26996 KB Output is correct
17 Correct 549 ms 26732 KB Output is correct
18 Correct 603 ms 26860 KB Output is correct
19 Correct 489 ms 26476 KB Output is correct
20 Correct 627 ms 26092 KB Output is correct
21 Correct 660 ms 27756 KB Output is correct
22 Correct 629 ms 27776 KB Output is correct
23 Correct 646 ms 27884 KB Output is correct
24 Correct 655 ms 27756 KB Output is correct
25 Correct 673 ms 27140 KB Output is correct