oj.uz

Submission #680300

# Submission time Handle Problem Language Result Execution time Memory
680300 2023-01-10T14:25:21 Z ntarsis Election (BOI18_election) C++17
100 / 100
 500 ms 27976 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 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 46 ms 5460 KB Output is correct
7 Correct 44 ms 5588 KB Output is correct
8 Correct 45 ms 5584 KB Output is correct
9 Correct 61 ms 5648 KB Output is correct
10 Correct 46 ms 5500 KB Output is correct
11 Correct 48 ms 5660 KB Output is correct
12 Correct 45 ms 5708 KB Output is correct
13 Correct 46 ms 5708 KB Output is correct
14 Correct 50 ms 5692 KB Output is correct
15 Correct 51 ms 5648 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 46 ms 5460 KB Output is correct
7 Correct 44 ms 5588 KB Output is correct
8 Correct 45 ms 5584 KB Output is correct
9 Correct 61 ms 5648 KB Output is correct
10 Correct 46 ms 5500 KB Output is correct
11 Correct 48 ms 5660 KB Output is correct
12 Correct 45 ms 5708 KB Output is correct
13 Correct 46 ms 5708 KB Output is correct
14 Correct 50 ms 5692 KB Output is correct
15 Correct 51 ms 5648 KB Output is correct
16 Correct 441 ms 26768 KB Output is correct
17 Correct 442 ms 26460 KB Output is correct
18 Correct 404 ms 26700 KB Output is correct
19 Correct 342 ms 26240 KB Output is correct
20 Correct 457 ms 26068 KB Output is correct
21 Correct 461 ms 27644 KB Output is correct
22 Correct 500 ms 27616 KB Output is correct
23 Correct 466 ms 27976 KB Output is correct
24 Correct 455 ms 27532 KB Output is correct
25 Correct 454 ms 26984 KB Output is correct