Submission #67953

#	Time	Username	Problem	Language	Result	Execution time	Memory
67953		aome	Election (BOI18_election)	C++17	100 / 100	2387 ms	129464 KiB

election

#include <bits/stdc++.h>

using namespace std;

const int N = 500005;
const int INF = 1e9;

int n, m;
string s;
int sum[N];

struct Data {
	int sum, mx, cnt;

	Data() { sum = mx = cnt = 0; }
};

struct SegmentTree {
	struct Node {
		int sum, mx;
		vector<int> f;
	};

	Node T[N << 2];

	#define mid ((l + r) >> 1)

	void build(int i, int l, int r) {
		sum[l - 1] = 0;
		for (int j = l; j <= r; ++j) {
			sum[j] = sum[j - 1] + (s[j] == 'C' ? 1 : -1);
		}
		T[i].sum = sum[r];
		int cur = 0;
		vector<int> vec;
		for (int j = l - 1; j <= r; ++j) {
			if (sum[j] == cur) vec.push_back(j), --cur;
		}
		int sz = vec.size();
		T[i].f.assign(sz, 0);
		for (int j = 0; j < sz; ++j) {
			int mx = -INF;
			int tmp = j == sz - 1 ? r : vec[j + 1] - 1;
			for (int k = vec[j]; k <= tmp; ++k) {
				mx = max(mx, sum[k]);
			}
			T[i].f[j] = mx + 1;
		}
		for (int j = sz - 2; j >= 0; --j) T[i].f[j] = max(T[i].f[j], T[i].f[j + 1] + 1);
		int mx = 0;
		for (int j = 0; j < sz; ++j) {
			int tmp = j == sz - 1 ? r : vec[j + 1] - 1;
			for (int k = vec[j]; k <= tmp; ++k) mx = max(mx, sum[k]);
			T[i].f[j] = max(T[i].f[j], mx);
		}
		T[i].mx = mx;
		if (l == r) return;
		build(i << 1, l, mid);
		build(i << 1 | 1, mid + 1, r);
	}

	void get(int i, int l, int r, int L, int R, Data &x) {
		if (l > R || L > r) return;
		if (L <= l && r <= R) {
			int tmp = x.sum + 1;
			int sz = T[i].f.size();
			if (sz <= tmp) {
				x.mx = max(x.mx, x.sum + T[i].mx), x.sum += T[i].sum; return;
			}
			x.mx = max(x.mx, x.sum + T[i].f[tmp]);
			x.sum += T[i].sum + sz - tmp;
			x.cnt += sz - tmp;
			return;
		}
		get(i << 1, l, mid, L, R, x);
		get(i << 1 | 1, mid + 1, r, L, R, x);
	}

	#undef mid
} IT;

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> s, s = ' ' + s;
	IT.build(1, 1, n);
	cin >> m;
	while (m--) {
		int l, r; cin >> l >> r;
		Data tmp;
		IT.get(1, 1, n, l, r, tmp);
		cout << tmp.cnt + tmp.mx - tmp.sum << '\n';
	}
}

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