oj.uz

Submission #129865

# Submission time Handle Problem Language Result Execution time Memory
129865 2019-07-13T11:36:46 Z Vlatko Election (BOI18_election) C++14
100 / 100
 2345 ms 49588 KB 
#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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12152 KB Output is correct
2 Correct 18 ms 12280 KB Output is correct
3 Correct 17 ms 12152 KB Output is correct
4 Correct 17 ms 12280 KB Output is correct
5 Correct 17 ms 12280 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12152 KB Output is correct
2 Correct 18 ms 12280 KB Output is correct
3 Correct 17 ms 12152 KB Output is correct
4 Correct 17 ms 12280 KB Output is correct
5 Correct 17 ms 12280 KB Output is correct
6 Correct 253 ms 17896 KB Output is correct
7 Correct 226 ms 17160 KB Output is correct
8 Correct 227 ms 17272 KB Output is correct
9 Correct 228 ms 17784 KB Output is correct
10 Correct 259 ms 17784 KB Output is correct
11 Correct 258 ms 18040 KB Output is correct
12 Correct 250 ms 18040 KB Output is correct
13 Correct 254 ms 18328 KB Output is correct
14 Correct 247 ms 17984 KB Output is correct
15 Correct 245 ms 17784 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12152 KB Output is correct
2 Correct 18 ms 12280 KB Output is correct
3 Correct 17 ms 12152 KB Output is correct
4 Correct 17 ms 12280 KB Output is correct
5 Correct 17 ms 12280 KB Output is correct
6 Correct 253 ms 17896 KB Output is correct
7 Correct 226 ms 17160 KB Output is correct
8 Correct 227 ms 17272 KB Output is correct
9 Correct 228 ms 17784 KB Output is correct
10 Correct 259 ms 17784 KB Output is correct
11 Correct 258 ms 18040 KB Output is correct
12 Correct 250 ms 18040 KB Output is correct
13 Correct 254 ms 18328 KB Output is correct
14 Correct 247 ms 17984 KB Output is correct
15 Correct 245 ms 17784 KB Output is correct
16 Correct 2183 ms 47708 KB Output is correct
17 Correct 1991 ms 41396 KB Output is correct
18 Correct 2003 ms 44040 KB Output is correct
19 Correct 1907 ms 46164 KB Output is correct
20 Correct 2145 ms 46932 KB Output is correct
21 Correct 2296 ms 49060 KB Output is correct
22 Correct 2153 ms 48900 KB Output is correct
23 Correct 2345 ms 49588 KB Output is correct
24 Correct 2158 ms 48888 KB Output is correct
25 Correct 2100 ms 47992 KB Output is correct