Submission #129865

#	Time	Username	Problem	Language	Result	Execution time	Memory
129865		Vlatko	Election (BOI18_election)	C++14	100 / 100	2345 ms	49588 KiB

election

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;


const int inf = 1e9;
const int maxn = 500005;
const int maxq = 500005;

struct Node {
	int sum, msuf;
};

int n, q;
int a[maxn];
Node tree[4*maxn];

int answer[maxq];
int ql[maxq], qr[maxq];
vector<int> query[maxn]; // query[i] = ids of queries such that L=i

void merge(Node& v, Node& l, Node& r) {
	v.sum = l.sum + r.sum;
	v.msuf = min(l.msuf + r.sum, r.msuf);
}

void build(int v, int tl, int tr) {
	if (tl == tr) {
		tree[v].sum = a[tl];
		tree[v].msuf = min(0, a[tl]);
		return;
	}
	int tm = (tl + tr) / 2;
	build(2*v, tl, tm);
	build(2*v+1, tm+1, tr);
	merge(tree[v], tree[2*v], tree[2*v+1]);
}

void update(int v, int tl, int tr, int pos, int val) {
	if (tl == tr) {
		tree[v].sum = val;
		tree[v].msuf = min(0, val);
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos <= tm) {
		update(2*v, tl, tm, pos, val);
	} else {
		update(2*v+1, tm+1, tr, pos, val);
	}
	merge(tree[v], tree[2*v], tree[2*v+1]);
}

int get_sum(int v, int tl, int tr, int l, int r) {
	if (l > r) {
		return 0;
	}
	if (l <= tl && tr <= r) {
		return tree[v].sum;
	}
	int tm = (tl + tr) / 2;
	return get_sum(2*v, tl, tm, l, min(r, tm))
	       + get_sum(2*v+1, tm+1, tr, max(l, tm+1), r);
}

inline void print(int v) {
	while (v > 1) {
		cout << "  ";
		v /= 2;
	}
}

int min_suffix(int v, int tl, int tr, int l, int r) {
	// print(v);
	// cout << "min_suffix(v=" << v << ", tl=" << tl << ", tr=" << tr << ", l=" << l << ", r=" << r << ")" << endl;
	if (l > r) {
		// print(v);
		// cout << "res=" << inf << endl;
		return inf;
	}
	if (l <= tl && tr <= r) {
		// print(v);
		// cout << "res=" << tree[v].msuf << endl;
		return tree[v].msuf;
	}
	int tm = (tl + tr) / 2;
	int res1 = min_suffix(2*v, tl, tm, l, min(r, tm))
	            + get_sum(2*v+1, tm+1, tr, max(l, tm+1), r);
	int res2 = min_suffix(2*v+1, tm+1, tr, max(l, tm+1), r);
	// print(v);
	// cout << "res1=" << res1 << " res2=" << res2 << endl;
	return min(res1, res2);
}

int main() {
	// ios::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		char ch;
		cin >> ch;
		a[i] = (ch == 'C') ? 1 : -1;
	}
	cin >> q;
	for (int i = 1; i <= q; ++i) {
		cin >> ql[i] >> qr[i];
		query[ql[i]].push_back(i);
	}
	build(1, 1, n);
	vector<int> stk; // which positions should be removed (decreasing order)
	for (int L = n; L >= 1; --L) {
		// cout << "L=" << L << endl;
		if (a[L] == 1 && !stk.empty()) {
			int i = stk.back();
			stk.pop_back();
			update(1, 1, n, i, a[i]); // original value
			// cout << "removed " << i << " from stack, updated a[" << i << "] to " << a[i] << endl;
		} else if (a[L] == -1) {
			stk.push_back(L);
			update(1, 1, n, L, 0); // set it to 0
			// cout << "added " << L << " to stack, updated a[" << L << "] to " << 0 << endl;
		}
		for (int i : query[L]) {
			int R = qr[i];
			auto it = upper_bound(stk.rbegin(), stk.rend()	, R);
			answer[i] = 0;
			answer[i] += distance(stk.rbegin(), it); // which votes will be removed by pass from L to R
			int min_suffix_here = min_suffix(1, 1, n, L, R);
			answer[i] += -min_suffix_here; // which will be removed from R to L (assuming the previous pass was done)
			// cout << "processing query " << i << " (L=" << L << ", R=" << R << ")" << endl;
			// cout << "it distance=" << distance(stk.rbegin(), it) << ", min suffix=" << min_suffix_here << endl;
			// cout << endl;
		}
	}
	for (int i = 1; i <= q; ++i) {
		cout << answer[i] << '\n';
	}
}

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