Submission #1240457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240457		MateiKing80	Election (BOI18_election)	C++20	100 / 100	726 ms	22260 KiB

election

#include <bits/stdc++.h>

using namespace std;

const int N = 500005;

struct node {
	int l, r, ans, sum;
} aint[4 * N + 5];

node join(node a, node b) {
	node c;
	c.l = max(a.l, a.sum + b.l);
	c.r = max(b.r, b.sum + a.r);
	c.sum = a.sum + b.sum;
	c.ans = max({a.ans + b.sum, a.sum + b.ans, a.l + b.r});
	return c;
}

void build(int pos, int st, int dr, string &s) {
	if (st == dr) {
		if (s[st - 1] == 'C')
			aint[pos] = {0, 0, 0, -1};
		else
			aint[pos] = {1, 1, 1, 1};
		return;
	}
	int mid = (st + dr) >> 1;
	build (2 * pos, st, mid, s);
	build (2 * pos + 1, mid + 1, dr, s);
	aint[pos] = join(aint[2 * pos], aint[2 * pos + 1]);
}

node query(int pos, int st, int dr, int l, int r) {
	if (l <= st && dr <= r)
		return aint[pos];
	int mid = (st + dr) >> 1;
	if (r <= mid)
		return query(2 * pos, st, mid, l, r);
	else if (mid < l)
		return query(2 * pos + 1, mid + 1, dr, l, r);
	return join(query(2 * pos, st, mid, l, r), query(2 * pos + 1, mid + 1, dr, l, r));
}

signed main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	build(1, 1, n, s);
	int q;
	cin >> q;
	vector<int> last(n, q + 1);
	while (q --) {
		int l, r;
		cin >> l >> r;
		cout << query(1, 1, n, l, r).ans << '\n';
	}
}

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