oj.uz

Submission #71543

# Submission time Handle Problem Language Result Execution time Memory
71543 2018-08-25T05:36:46 Z aome Election (BOI18_election) C++17
100 / 100
 551 ms 105636 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 500005;
const int INF = 1e9;

struct Node {
	int sum, val;

	Node() { sum = val = 0; }

	void dbg() { cout << "#node " << sum << ' ' << val << '\n'; }
};

struct Query {
	int l, r, id;

	bool operator < (const Query& rhs) const {
		return l > rhs.l;
	}
};

int n, q, res[N];
string s;
Node T[N * 2];
vector<Query> queries;

Node combine(Node &x, Node &y) {
	Node ret;
	ret.sum = x.sum + y.sum;
	ret.val = min(y.val, x.val + y.sum);
	return ret;
}

void upd(int p, int x) {
	// cout << "#upd " << p << ' ' << x << '\n';
	p += n, T[p].sum = T[p].val = x;
	while (p > 1) {
		p >>= 1;
		T[p] = combine(T[p << 1], T[p << 1 | 1]);
		// cout << "#p " << p << '\n';
		// T[p].dbg();
	}
}

int get(int l, int r) {
	// cout << "#get " << l << ' ' << r << '\n';
	Node Tl, Tr;
	for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
		// cout << l << ' ' << r << '\n';
		if (l & 1) Tl = combine(Tl, T[l++]);
		if (!(r & 1)) Tr = combine(T[r--], Tr);
	}
	// Tl.dbg(), Tr.dbg();
	return combine(Tl, Tr).val;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> s >> q, s = ' ' + s;
	for (int i = 1; i <= q; ++i) {
		int l, r; cin >> l >> r;
		queries.push_back({l, r, i});
	}
	sort(queries.begin(), queries.end());
	int ptr = n;
	vector<int> vec;
	for (auto i : queries) {
		while (ptr >= i.l) {
			if (s[ptr] == 'T') vec.push_back(ptr);
			else {
				upd(ptr, 1);
				if (vec.size()) {
					int p = vec.back();
					upd(p, -1), vec.pop_back();
				}
			}
			--ptr;
		}
		// cout << get(i.l, i.r) << '\n';
		res[i.id] = upper_bound(vec.rbegin(), vec.rend(), i.r) - vec.rbegin() - get(i.l, i.r);
	}
	for (int i = 1; i <= q; ++i) cout << res[i] << '\n';
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8312 KB Output is correct
2 Correct 11 ms 8340 KB Output is correct
3 Correct 10 ms 8488 KB Output is correct
4 Correct 11 ms 8560 KB Output is correct
5 Correct 12 ms 8584 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8312 KB Output is correct
2 Correct 11 ms 8340 KB Output is correct
3 Correct 10 ms 8488 KB Output is correct
4 Correct 11 ms 8560 KB Output is correct
5 Correct 12 ms 8584 KB Output is correct
6 Correct 68 ms 11260 KB Output is correct
7 Correct 53 ms 12200 KB Output is correct
8 Correct 51 ms 13168 KB Output is correct
9 Correct 63 ms 14088 KB Output is correct
10 Correct 56 ms 15100 KB Output is correct
11 Correct 72 ms 16048 KB Output is correct
12 Correct 73 ms 17000 KB Output is correct
13 Correct 71 ms 17940 KB Output is correct
14 Correct 59 ms 18896 KB Output is correct
15 Correct 77 ms 20096 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 8312 KB Output is correct
2 Correct 11 ms 8340 KB Output is correct
3 Correct 10 ms 8488 KB Output is correct
4 Correct 11 ms 8560 KB Output is correct
5 Correct 12 ms 8584 KB Output is correct
6 Correct 68 ms 11260 KB Output is correct
7 Correct 53 ms 12200 KB Output is correct
8 Correct 51 ms 13168 KB Output is correct
9 Correct 63 ms 14088 KB Output is correct
10 Correct 56 ms 15100 KB Output is correct
11 Correct 72 ms 16048 KB Output is correct
12 Correct 73 ms 17000 KB Output is correct
13 Correct 71 ms 17940 KB Output is correct
14 Correct 59 ms 18896 KB Output is correct
15 Correct 77 ms 20096 KB Output is correct
16 Correct 469 ms 36856 KB Output is correct
17 Correct 469 ms 44160 KB Output is correct
18 Correct 422 ms 51904 KB Output is correct
19 Correct 397 ms 58896 KB Output is correct
20 Correct 475 ms 65932 KB Output is correct
21 Correct 551 ms 75472 KB Output is correct
22 Correct 496 ms 82972 KB Output is correct
23 Correct 485 ms 91864 KB Output is correct
24 Correct 472 ms 98312 KB Output is correct
25 Correct 481 ms 105636 KB Output is correct