Submission #67666

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

election

#include <bits/stdc++.h>

using namespace std;

const int N = 500005;

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) {
	int k = lg2[r - l + 1];
	return max(rmq[t][k][l], rmq[t][k][r - (1 << k) + 1]);
}

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], 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> tmp = get(1, l, r);
		int res = max(0, tmp.first + fc[1][r + 1] - ft[1][r + 1]);
		if (l < tmp.second) {
			res += max(0, get(0, l, tmp.second - 1).first + fc[0][l - 1] - ft[0][l - 1]);
		}
		cout << res << '\n';
	}
}

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