Submission #1137357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137357		vuavisao	Election (BOI18_election)	C++20	0 / 100	1 ms	576 KiB

election

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

using ll = long long;

const int N = 500'000 + 10;

struct RMQ {
	int n, Lg;
	int specialValue;
	vector<vector<int>> rmq;
	function<int(int, int)> comb;

	RMQ() {};
	RMQ(int _n, function<int(int, int)> _comb) : n(_n), comb(_comb) {
		assert(comb);
		Lg = __lg(n);
		rmq.resize(Lg + 5, vector<int>(n + 10, 0));
	};
	
	RMQ(int _n, int a[], function<int(int, int)> _comb) : n(_n), comb(_comb) {
		assert(comb);
		Lg = __lg(n);
		assert((1 << (Lg + 1)) > n);
		rmq.resize(Lg + 5, vector<int>(n + 10, 0));
		apply(a);
	};

	void apply(int a[]) {
		for (int i = 1; i <= n; ++ i) rmq[0][i] = a[i];

		for (int lg = 1; lg <= Lg; ++ lg) {
			for (int i = 1; i + (1 << lg) - 1 <= n; ++ i) {
				rmq[lg][i] = comb(rmq[lg - 1][i], rmq[lg - 1][i + (1 << (lg - 1))]);
			}
		}
	}

	int getRmq(int l, int r) {
		if (l > r) return specialValue;
		int k = 31 - __builtin_clz(r - l + 1);
		return comb(rmq[k][l], rmq[k][r - (1 << k) + 1]);
	}

	void walk_on_rmq() {
		// custom
	}

	void setSpecialValue(int val) {
		specialValue = val;
	}
};

int minComb(int lhs, int rhs) { return min(lhs, rhs); }
int maxComb(int lhs, int rhs) { return max(lhs, rhs); }
int gcdComb(int lhs, int rhs) { return __gcd(lhs, rhs); }

int n, q;
string s;
pair<int, int> qq[N];

int mark[N];
int pred[N];
int res[N];

void solve() {
	cin >> n >> s;
	for (int i = 1; i <= n; ++i) {
		mark[i] = (s[i - 1] == 'C' ? 1 : -1);
	}
	cin >> q;
	for (int i = 1; i <= q; ++i) {
		auto& [l, r] = qq[i];
		cin >> l >> r;
	}
	fill(res + 1, res + 1 + n, true);
	for (int turn = 0; turn < 2; ++turn) {
		for (int i = 1; i <= n; ++i) {
			pred[i] = pred[i - 1] + mark[i];
		}
		RMQ rmq(n, pred, minComb);
		for (int i = 1; i <= q; ++i) {
			auto& [l, r] = qq[i];
			res[i] = max(res[i], max(0, pred[l - 1] - rmq.getRmq(l, r)));
			l = n - l + 1;
			r = n - r + 1;
			swap(l, r);
		}
		reverse(mark + 1, mark + 1 + n);
	}
	for (int i = 1; i <= q; ++i) cout << res[i] << '\n';
}

int32_t main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr); std::cout.tie(nullptr);
	// int t; cin >> t;
	int t = 1;
	while (t-- > 0) {
		solve();
		// cout << '\n';
	}
	return (0 ^ 0);
}

/// Code by vuavisao

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