Submission #955688

#	Time	Username	Problem	Language	Result	Execution time	Memory
955688		MinaRagy06	Election (BOI18_election)	C++17	0 / 100	2 ms	348 KiB

election

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n;
	cin >> n;
	string s;
	cin >> s;
	int nxt[n]{}, lst = n, sz[n]{}, cnt = 0;
	for (int i = n - 1; i >= 0; i--) {
		nxt[i] = lst;
		cnt += s[i] == 'T';
		if (i - 1 >= 0 && s[i - 1] != s[i]) {
			lst = i;
		}
		if (i - 1 < 0 || s[i - 1] == 'C') {
			sz[i] = cnt;
			cnt = 0;
		}
	}
	int prv[n]{}, prf[n + 1]{};
	lst = -1;
	for (int i = 0; i < n; i++) {
		prv[i] = lst;
		if (i + 1 < n && s[i + 1] != s[i]) {
			lst = i;
		}
		prf[i + 1] = prf[i] + (s[i] == 'C');
	}
	auto sum = [&] (int l, int r) {
		return prf[r + 1] - prf[l];
	};
	int q;
	cin >> q;
	int ans[q]{};
	for (int k = 0; k < q; k++) {
		int l, r;
		cin >> l >> r;
		l--, r--;
		if (s[l] == 'T') {
			if (nxt[l] > r) {
				ans[k] = r - l + 1;
				continue;
			}
			ans[k] += nxt[l] - l;
			l = nxt[l];
		}
		if (s[r] == 'T') {
			ans[k] += r - prv[r];
			r = prv[r];
		}
		for (int i = l; i <= r; i++) {
			ans[k] += max(0, sz[i] - min(sum(l, i), sum(i, r)));
		}
	}
	for (int i = 0; i < q; i++) {
		cout << ans[i] << '\n';
	}
	return 0;
}

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