Submission #888833

#	Time	Username	Problem	Language	Result	Execution time	Memory
888833		iee	Election (BOI18_election)	C++17	100 / 100	311 ms	28232 KiB

election

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 5;
int n, Q;
char s[N];
struct info {
	int ans, sum, pre, suf;
} tr[N << 2];
info pushup(info l, info r) {
	info u;
	u.ans = max({l.pre + r.suf, l.sum + r.ans, r.sum + l.ans});
	u.sum = l.sum + r.sum;
	u.pre = max(l.pre, l.sum + r.pre);
	u.suf = max(r.suf, r.sum + l.suf);
	return u;
}
void build(int u = 1, int l = 1, int r = n) {
	if (l == r) {
		tr[u].sum = s[l];
		tr[u].ans = tr[u].pre = tr[u].suf = max<int>(s[l], 0);
		return;
	}
	int mid = (l + r) / 2;
	build(u * 2, l, mid), build(u * 2 + 1, mid + 1, r);
	tr[u] = pushup(tr[u * 2], tr[u * 2 + 1]);
}
info query(int ql, int qr, int u = 1, int l = 1, int r = n) {
	if (l >= ql && r <= qr) {
		return tr[u];
	}
	int mid = (l + r) / 2;
	if (ql > mid) return query(ql, qr, u * 2 + 1, mid + 1, r);
	if (qr <= mid) return query(ql, qr, u * 2, l, mid);
	return pushup(query(ql, qr, u * 2, l, mid), query(ql, qr, u * 2 + 1, mid + 1, r));
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		s[i] = (s[i] == 'T' ? 1 : -1);
	}
	build();
	cin >> Q;
	while (Q--) {
		int l, r;
		cin >> l >> r;
		cout << query(l, r).ans << "\n";
	}
	return 0;
}

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