Submission #958052

#	Time	Username	Problem	Language	Result	Execution time	Memory
958052		MinaRagy06	Election (BOI18_election)	C++17	100 / 100	403 ms	46164 KiB

election

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define md ((l + r) >> 1)

const int N = 1'000'005;
int a[N];
struct node {
	int s, prf, suf, ans;
	node() {
		s = prf = suf = ans = 0;
	}
	node(int x) {
		s = x;
		prf = suf = ans = max(x, 0);
	}
	friend node operator+(const node &l, const node &r) {
		node ret;
		ret.s = l.s + r.s;
		ret.prf = max(l.prf, l.s + r.prf);
		ret.suf = max(r.suf, l.suf + r.s);
		ret.ans = max({l.ans + r.s, l.s + r.ans, l.prf + r.suf});
		return ret;
	}
} seg[1 << 21];
void build(int i, int l, int r) {
	if (l == r) {
		seg[i] = a[l];
		return;
	}
	build(i << 1, l, md);
	build(i << 1 | 1, md + 1, r);
	seg[i] = seg[i << 1] + seg[i << 1 | 1];
}
node get(int i, int l, int r, int s, int e) {
	if (s <= l && r <= e) {
		return seg[i];
	}
	if (r < s || e < l) {
		return node();
	}
	return get(i << 1, l, md, s, e) + get(i << 1 | 1, md + 1, r, s, e);
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		char c;
		cin >> c;
		a[i] = (c == 'T'? 1 : -1);
	}
	build(1, 0, n - 1);
	int q;
	cin >> q;
	while (q--) {
		int l, r;
		cin >> l >> r;
		l--, r--;
		cout << get(1, 0, n - 1, l, r).ans << '\n';
	}
	return 0;
}

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