Submission #1289304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289304		itaykarny	Election (BOI18_election)	C++20	100 / 100	621 ms	100752 KiB

election

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

vll arr;

struct Node {
	ll l, r;
	Node* lp, * rp;
	ll sum_intreval = 0, min_suf = 0;

	Node(ll L, ll R) {
		l = L, r = R;
		if (l + 1 == r) {
			sum_intreval = arr[l];
			min_suf = arr[l];
			return;
		}
		lp = new Node(l, (l + r) / 2);
		rp = new Node((l + r) / 2, r);
		pull();
	}

	void pull() {
		sum_intreval = lp->sum_intreval + rp->sum_intreval;
		min_suf = min(rp->min_suf, rp->sum_intreval + lp->min_suf);
	}

	void update(ll start, ll x) {
		if (start < l || start >= r) { return; }
		if (start == l && start + 1 == r) {
			sum_intreval = x;
			min_suf = x;
			return;
		}
		lp->update(start, x);
		rp->update(start, x);
		pull();
	}

	ll solve(ll start, ll end, ll& sum_to_now) {
		if (start >= r || end <= l) { return 1e18; }
		if (start <= l && r <= end) {
			sum_to_now += sum_intreval;
			return sum_to_now + min_suf - sum_intreval;
		}
		ll ans = 1e18;
		ans = min(ans, rp->solve(start, end, sum_to_now));
		ans = min(ans, lp->solve(start, end, sum_to_now));
		return ans;
	}

};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	ll n;
	cin >> n;
	string s;
	cin >> s;
	arr.resize(n);
	for (ll i = 0; i < n; i++) {
		if (s[i] == 'C') {
			arr[i] = 1;
		}
		else {
			arr[i] = -1;
		}
	}
	ll q;
	cin >> q;
	vector<vpll> quries(n);
	for (ll i = 0; i < q; i++) {
		ll l, r;
		cin >> l >> r;
		l--, r--;
		quries[l].push_back({ r, i });
	}
	Node* root = new Node(0, n);
	vll index;
	vll ans(q);
	for (ll i = n - 1; i >= 0; i--) {
		if (arr[i] == 1) {
			if (!index.empty()) {
				root->update(index.back(), -1);
				index.pop_back();
			}
		}
		else {
			index.push_back(i);
			root->update(i, 0);
		}
		ll sum_to_now = 0;
		for (auto j : quries[i]) {
			sum_to_now = 0;
			ans[j.second] -= min(root->solve(i, j.first + 1, sum_to_now), ll(0));
			ans[j.second] += index.end() - lower_bound(index.begin(), index.end(), j.first, greater<ll>());
		}
	}
	for (ll i = 0; i < q; i++) {
		cout << ans[i] << '\n';
	}
}

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