Submission #1137361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137361		vuavisao	Election (BOI18_election)	C++20	28 / 100	3092 ms	2216 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];

int temp[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;
	}
	
	for (int _ = 1; _ <= q; ++_) {
		const auto& [l, r] = qq[_];

		for (int i = 1; i <= n; ++i) temp[i] = mark[i];
		int sum = 0;
		for (int i = l; i <= r; ++i) {
			sum += temp[i];
			if (sum < 0) {
				++sum;
				++res[_];
				temp[i] = 0;
			}
		}
		// for (int i = 1; i <= n; ++i) cerr << temp[i] << " \n"[i == n];
		// cerr << _ << ' ' << res[_] << '\n';
		sum = 0;
		for (int i = r; i >= l; --i) {
			sum += temp[i];
			if (sum < 0) {
				++sum;
				++res[_];
				temp[i] = 0;
			}
		}
	}

	// 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: 28 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18