제출 #1241121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241121		ssitaram	Election (BOI18_election)	C++20	82 / 100	1356 ms	321780 KiB

election

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

typedef long long ll;
typedef long double ld;

struct segtree {
	int n;
	vector<int> more;
	vector<vector<int>> rem, frback, frfront, frback2;

	segtree(int sz) {
		n = 1;
		while (n < sz) n *= 2;
		more.resize(2 * n - 1);
		rem.resize(2 * n - 1);
		frback.resize(2 * n - 1);
		frfront.resize(2 * n - 1);
		frback2.resize(2 * n - 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, string& s) {
		if (r != l + 1) {
			int m = (l + r) / 2;
			assign(node * 2 + 1, l, m, s);
			assign(node * 2 + 2, m, r, s);
		}
		int here = 0;
		for (int i = l; i < r; ++i) {
			here += eq(s[i]);
			more[node] += 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);
		frback[node][r - l] = 0;
		here = 0;
		int idx = rem[node].size() - 1;
		for (int i = r - 1; i >= l; --i) {
			frback2[node][i - l] = frback2[node][i - l + 1] + eq(s[i]);
			if (idx < 0 || i - l != rem[node][idx]) {
				here += eq(s[i]);
			} else {
				--idx;
				++frback2[node][i - l];
			}
			frback[node][i - l] = frback[node][i - l + 1] + (here < 0);
			if (here < 0) ++frback2[node][i - l];
			here = max(here, 0);
		}
	}


	void assign(string& s) {
		while (s.size() < n) s += '_';
		assign(0, 0, n, s);
	}

	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 += more[r[i].first] + 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 = frback[r[i].first][0];
				ex -= min(ex, here);
				remove[i] += ex;
			} else {
				ex = 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 + more[r[i].first] + 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: 0 / 18