Submission #159631

#	Time	Username	Problem	Language	Result	Execution time	Memory
159631		iefnah06	Election (BOI18_election)	C++11	100 / 100	1298 ms	56940 KiB

election

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

const int MAXN = 5.1e5;
int N, Q;
string S;
int pref[MAXN];

struct seg {
	seg* ch[2];
	int incr;
	int maxVal;
};
seg nodes[MAXN*2];
int V;

void propagate(seg* n) {
	for (int i = 0; i < 2; i++) {
		n->ch[i]->maxVal += n->incr;
		n->ch[i]->incr += n->incr;
	}
	n->incr = 0;
}

void update(seg* n) {
	n->maxVal = max(n->ch[0]->maxVal, n->ch[1]->maxVal);
}

seg* build(int x = 0, int y = N+1) {
	seg* n = &nodes[V++];
	if (y - x == 1) {
		n->maxVal = pref[x];
	} else {
		int z = (x + y) / 2;
		n->ch[0] = build(x, z);
		n->ch[1] = build(z, y);
		update(n);
	}
	return n;
}

void update(int l, int r, int v, seg* n, int x = 0, int y = N+1) {
	if (l <= x && y <= r) {
		n->maxVal += v;
		n->incr += v;
	} else {
		propagate(n);
		int z = (x + y) / 2;
		if (l < z) {
			update(l, r, v, n->ch[0], x, z);
		}
		if (z < r) {
			update(l, r, v, n->ch[1], z, y);
		}
		update(n);
	}
}

int query(int l, int r, seg* n, int x = 0, int y = N+1) {
	if (l <= x && y <= r) {
		return n->maxVal;
	} else {
		propagate(n);
		int ans = -MAXN;
		int z = (x + y) / 2;
		if (l < z) {
			ans = max(ans, query(l, r, n->ch[0], x, z));
		}
		if (z < r) {
			ans = max(ans, query(l, r, n->ch[1], z, y));
		}
		return ans;
	}
}

int bit[MAXN];
void update(int i, int v) {
	for (i++; i <= N+5; i += (i & -i)) {
		bit[i] += v;
	}
}
int query(int i) {
	int ans = 0;
	for (; i; i -= (i & -i)) {
		ans += bit[i];
	}
	return ans;
}
int query(int l, int r) { // half open
	return query(r) - query(l);
}

const int MAXQ = 5.1e5;
int ans[MAXQ];
vector<pair<int, int>> queries[MAXN];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> S;
	pref[0] = 0;
	for (int i = 0; i < N; i++) {
		pref[i+1] = pref[i] + (S[i] == 'C' ? +1 : -1);
	}
	seg* root = build();

	cin >> Q;
	for (int q = 0; q < Q; q++) {
		int l, r; cin >> l >> r; l--;
		queries[l].emplace_back(r, q);
	}

	vector<int> st;
	for (int x = N; x >= 0; x--) {
		while (!st.empty() && pref[st.back()] >= pref[x]) {
			int i = st.back();
			update(i, -1);
			update(i, N+1, -1, root);
			st.pop_back();
		}
		for (auto q : queries[x]) {
			int r = q.first;
			int ind = q.second;
			ans[ind] = query(x+1, r+1) + query(x, r+1, root) - query(r, r+1, root);
		}
		{
			update(x, 1);
			update(x, N+1, 1, root);
			st.push_back(x);
		}
	}
	for (int q = 0; q < Q; q++) {
		cout << ans[q] << '\n';
	}

	return 0;
}

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