Submission #67737

#	Time	Username	Problem	Language	Result	Execution time	Memory
67737		aome	Election (BOI18_election)	C++17	0 / 100	8 ms	888 KiB

election

#include <bits/stdc++.h>

using namespace std;

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

int n, m;
int lg2[N];
int fc[2][N], ft[2][N];
pair<int, int> rmq[2][20][N];
string s;

pair<int, int> get(int t, int l, int r) {
	if (l > r) return {-INF, 0};
	int k = lg2[r - l + 1];
	return max(rmq[t][k][l], rmq[t][k][r - (1 << k) + 1]);
}

//ctctcct

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> s, s = ' ' + s;
	for (int i = 1; i <= n; ++i) {
		fc[0][i] = fc[0][i - 1] + (s[i] == 'C');
		ft[0][i] = ft[0][i - 1] + (s[i] == 'T');
	}
	for (int i = n; i >= 1; --i) {
		fc[1][i] = fc[1][i + 1] + (s[i] == 'C');
		ft[1][i] = ft[1][i + 1] + (s[i] == 'T');
	}
	for (int i = 2; i <= n; ++i) lg2[i] = lg2[i >> 1] + 1;
	for (int t = 0; t < 2; ++t) {
		for (int i = 1; i <= n; ++i) {
			rmq[t][0][i] = {ft[t][i] - fc[t][i], (t == 0) ? -i : i};
		}
		for (int i = 1; i < 20; ++i) {
			for (int j = 1; j + (1 << i) - 1 <= n; ++j) {
				rmq[t][i][j] = max(rmq[t][i - 1][j], rmq[t][i - 1][j + (1 << (i - 1))]);
			}
		}
	}
	cin >> m;
	while (m--) {
		int l, r; cin >> l >> r;
		pair<int, int> tmp0 = get(0, l, r);
		tmp0.first += -ft[0][l - 1] + fc[0][l - 1];
		tmp0.second = -tmp0.second;
		pair<int, int> tmp1 = get(1, l, r);
		tmp1.first += -ft[1][r + 1] + fc[1][r + 1];
		if (tmp0.first <= 0) tmp0.first = 0, tmp0.second = l - 1;
		if (tmp1.first <= 0) tmp1.first = 0, tmp1.second = r + 1;
		if (tmp0.first < tmp1.first) {
			tmp0 = get(0, l, tmp1.second - 1);
			tmp0.first += -ft[0][l - 1] + fc[0][l - 1];
			tmp0.first = max(0, tmp0.first);
		}
		else {
			tmp1 = get(1, tmp0.second + 1, r);
			tmp1.first += -ft[1][r + 1] + fc[1][r + 1];
			tmp1.first = max(0, tmp1.first);
		}
		cout << tmp0.first + tmp1.first << '\n';
	}
}

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