Submission #1241128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241128		ssitaram	Election (BOI18_election)	C++20	100 / 100	1142 ms	248380 KiB

election

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

typedef long long ll;
typedef long double ld;

struct segtree {
	int n;
	string s;
	vector<int> pref;
	vector<vector<int>> rem, frfront, frback2;

	segtree(int sz) {
		n = 1;
		while (n < sz) n *= 2;
		rem.resize(2 * n - 1);
		//frback.resize(2 * n - 1);
		frfront.resize(2 * n - 1);
		frback2.resize(2 * n - 1);
	}

	int over(int a, int b) {
		return pref[b] - (a == 0 ? 0 : pref[a - 1]);
	}

	int eq(char c) {
		if (c == 'C') return 1;
		if (c == 'T') return -1;
		return 0;
	}
	
	void assign(int node, int l, int r) {
		if (r != l + 1) {
			int m = (l + r) / 2;
			assign(node * 2 + 1, l, m);
			assign(node * 2 + 2, m, r);
		}
		int here = 0;
		for (int i = l; i < r; ++i) {
			here += eq(s[i]);
			if (here < 0) {
				here = 0;
				rem[node].push_back(i - l);
			}
			frfront[node].push_back((i == l ? 0 : frfront[node].back()) - eq(s[i]));
			frfront[node].back() = max(frfront[node].back(), 0);
		}
		//frback[node].resize(r - l + 1);
		frback2[node].resize(r - l + 1);
		here = 0;
		int idx = rem[node].size() - 1;
		for (int i = r - 1; i >= l; --i) {
			if (idx < 0 || i - l != rem[node][idx]) {
				here += eq(s[i]);
			} else {
				--idx;
			}
			//frback[node][i - l] = frback[node][i - l + 1] + (here < 0);
			here = max(here, 0);
			frback2[node][i - l] = here;
		}
	}


	void assign(string& ss) {
		s = ss;
		while (s.size() < n) s += '_';
		pref.resize(n);
		for (int i = 0; i < n; ++i) {
			pref[i] = (i == 0 ? 0 : pref[i - 1]) + eq(s[i]);
		}
		assign(0, 0, n);
	}

	void getr(int node, int l, int r, int a, int b, vector<pair<int, pair<int, int>>>& ra) {
		if (r <= a || l >= b) return;
		if (a <= l && r <= b) {
			ra.push_back({node, {l, r}});
			return;
		}
		int m = (l + r) / 2;
		getr(node * 2 + 1, l, m, a, b, ra);
		getr(node * 2 + 2, m, r, a, b, ra);
	}

	int ans(int a, int b) {
		vector<pair<int, pair<int, int>>> r;
		getr(0, 0, n, a, b, r);
		vector<int> remove(r.size());
		int here = 0;
		for (int i = 0; i < r.size(); ++i) {
			remove[i] = rem[r[i].first].size();
			remove[i] -= min(remove[i], here);
			here += over(r[i].second.first, r[i].second.second - 1) + remove[i];
		}
		here = 0;
		int res = 0;
		for (int i = r.size() - 1; i >= 0; --i) {
			int ihere = here;
			int ex;
			int lunused = rem[r[i].first].size() - remove[i] - 1;
			if (lunused == -1) {
				ex = (frback2[r[i].first][0] - over(r[i].second.first, r[i].second.second - 1)) - remove[i]; // frback[r[i].first][0];
				ex -= min(ex, here);
				remove[i] += ex;
			} else {
				ex = frback2[r[i].first][rem[r[i].first][lunused] + 1] - over(r[i].second.first + rem[r[i].first][lunused] + 1, r[i].second.second - 1) - remove[i]; //  frback[r[i].first][rem[r[i].first][lunused] + 1];
				int red = min(ex, here);
				ex -= red;
				here += frback2[r[i].first][rem[r[i].first][lunused] + 1] - red;
				remove[i] += ex;
				int ex2 = frfront[r[i].first][rem[r[i].first][lunused]];
				ex2 -= min(ex2, here);
				remove[i] += ex2;
			}
			res += remove[i];
			here = ihere + over(r[i].second.first, r[i].second.second - 1) + remove[i];
		}
		return res;
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;
	string s; cin >> s;
	segtree st(n);
	st.assign(s);
	int q; cin >> q;
	while (q--) {
		int l, r; cin >> l >> r;
		--l; --r;
		cout << st.ans(l, r + 1) << '\n';
	}
	return 0;
}

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