oj.uz

Submission #129868

# Submission time Handle Problem Language Result Execution time Memory
129868 2019-07-13T11:45:49 Z Vlatko Election (BOI18_election) C++14
100 / 100
 913 ms 50796 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;
	Node(int s, int m) : sum(s), msuf(m) {}
	Node() : sum(0), msuf(0) {}
};

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

int answer[maxq];
int ql[maxq], qr[maxq];
vector<int> queries[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]);
}

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

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];
		queries[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) {
		if (a[L] == 1 && !stk.empty()) {
			int i = stk.back();
			stk.pop_back();
			update(1, 1, n, i, a[i]); // original value
		} else if (a[L] == -1) {
			stk.push_back(L);
			update(1, 1, n, L, 0); // set it to 0
		}
		for (int i : queries[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
			answer[i] += -query(1, 1, n, L, R).msuf; // which will be removed from R to L (assuming the previous pass was done)
		}
	}
	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 27 ms 27896 KB Output is correct
2 Correct 27 ms 27896 KB Output is correct
3 Correct 27 ms 27896 KB Output is correct
4 Correct 29 ms 27900 KB Output is correct
5 Correct 28 ms 27896 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 27896 KB Output is correct
2 Correct 27 ms 27896 KB Output is correct
3 Correct 27 ms 27896 KB Output is correct
4 Correct 29 ms 27900 KB Output is correct
5 Correct 28 ms 27896 KB Output is correct
6 Correct 107 ms 31440 KB Output is correct
7 Correct 95 ms 30700 KB Output is correct
8 Correct 100 ms 30840 KB Output is correct
9 Correct 100 ms 31372 KB Output is correct
10 Correct 100 ms 31352 KB Output is correct
11 Correct 118 ms 31652 KB Output is correct
12 Correct 124 ms 31608 KB Output is correct
13 Correct 116 ms 31848 KB Output is correct
14 Correct 107 ms 31564 KB Output is correct
15 Correct 102 ms 31480 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 27896 KB Output is correct
2 Correct 27 ms 27896 KB Output is correct
3 Correct 27 ms 27896 KB Output is correct
4 Correct 29 ms 27900 KB Output is correct
5 Correct 28 ms 27896 KB Output is correct
6 Correct 107 ms 31440 KB Output is correct
7 Correct 95 ms 30700 KB Output is correct
8 Correct 100 ms 30840 KB Output is correct
9 Correct 100 ms 31372 KB Output is correct
10 Correct 100 ms 31352 KB Output is correct
11 Correct 118 ms 31652 KB Output is correct
12 Correct 124 ms 31608 KB Output is correct
13 Correct 116 ms 31848 KB Output is correct
14 Correct 107 ms 31564 KB Output is correct
15 Correct 102 ms 31480 KB Output is correct
16 Correct 836 ms 49244 KB Output is correct
17 Correct 667 ms 43256 KB Output is correct
18 Correct 735 ms 45392 KB Output is correct
19 Correct 731 ms 47528 KB Output is correct
20 Correct 810 ms 48136 KB Output is correct
21 Correct 913 ms 50368 KB Output is correct
22 Correct 817 ms 50168 KB Output is correct
23 Correct 899 ms 50796 KB Output is correct
24 Correct 813 ms 50136 KB Output is correct
25 Correct 775 ms 49256 KB Output is correct