Submission #1205636

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205636		cxm1024	Election (BOI18_election)	C++20	100 / 100	365 ms	18280 KiB

election

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
int n, Q, a[500010];
string s;
struct node {
	int mx, mn, val;
} t[500010 << 2];
const node operator + (const node x, const node y) {
	return {max(x.mx, y.mx), min(x.mn, y.mn), max(max(x.val, y.val), y.mx - x.mn)};
}
#define lson (now << 1)
#define rson (now << 1 | 1)
#define mid ((l + r) >> 1)
void build(int now, int l = 0, int r = n) {
	if (l == r) {t[now].mx = t[now].mn = a[l], t[now].val = 0; return;}
	build(lson, l, mid), build(rson, mid + 1, r);
	t[now] = t[lson] + t[rson];
}
node query(int now, int ql, int qr, int l = 0, int r = n) {
	if (ql <= l && qr >= r) return t[now];
	if (qr <= mid) return query(lson, ql, qr, l, mid);
	if (ql > mid) return query(rson, ql, qr, mid + 1, r);
	return query(lson, ql, qr, l, mid) + query(rson, ql, qr, mid + 1, r);
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> s, s = " " + s;
	for (int i = 1; i <= n; i++)
		a[i] = a[i - 1] + (s[i] == 'C' ? 1 : -1);
	build(1), cin >> Q;
	while (Q--) {
		int l, r;
		cin >> l >> r, l--;
		cout << query(1, l, r).val + a[l] - a[r] << "\n";
	}
	return 0;
}

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