oj.uz

Submission #935854

# Submission time Handle Problem Language Result Execution time Memory
935854 2024-02-29T17:22:31 Z SamNguyen Election (BOI18_election) C++14
100 / 100
 499 ms 52052 KB 
#include <bits/stdc++.h>
using namespace std;

struct Node {
	int sum, rems;

	Node(): sum(0), rems(0) {}

	Node(int v) {
		if (v >= 0)
			sum = v, rems = 0;
		else
			sum = 0, rems = 1;
	}

	Node(const Node &lnode, const Node &rnode) {
		int delta = min(lnode.rems, rnode.sum);
		rems = rnode.rems + lnode.rems - delta;
		sum = lnode.sum + rnode.sum - delta;
	}
};

template <int N, class AddableNode>
class SegmentTree {
private:
	int n;
	AddableNode st[4 * N];

	inline void push_up(int id) {
		st[id] = AddableNode(st[id << 1], st[id << 1 | 1]);
	}

	void update(int id, int l, int r, int i, int v) {
		if (r < i or i < l)
			return;
		if (l == r) {
			// cerr << "update " << i << ", v = " << v << endl;

			st[id] = Node(v);
			return;
		}

		int m = (l + r) >> 1;
		update(id << 1, l, m, i, v);
		update(id << 1 | 1, m + 1, r, i, v);
		push_up(id);
	}

	AddableNode get(int id, int l, int r, int left, int right) {
		if (r < left or right < l or right < left or r < l)
			return AddableNode();
		if (left <= l and r <= right)
			return st[id];
		int m = (l + r) >> 1;
		return AddableNode(
			get(id << 1, l, m, left, right),
			get(id << 1 | 1, m + 1, r, left, right)
		);
	}

public:	
	inline void init(int _n) {
		n = _n;
	}

	inline void update(int i, int v) { update(1, 1, n, i, v); }
	inline AddableNode get(int left, int right) { return get(1, 1, n, left, right); }
};

const int MAX = 5e5 + 7;
int N, Q;
char str[MAX];
vector<pair<int, int>> queries_by_l[MAX];

void input() {
	cin >> N >> (str + 1);
	cin >> Q;
	for (int q = 0; q < Q; q++) {
		int l, r; cin >> l >> r;
		queries_by_l[l].emplace_back(r, q);
	}
}

SegmentTree<MAX, Node> st;
void init() {
	st.init(N);
}

int ans[MAX];

void solve() {
	deque<int> de;
	for (int l = N; l >= 1; l--) {
		if (str[l] == 'T') {
			de.push_front(l);
		}
		else { // str[l] == 'C'
			if (not de.empty()) {
				int j = de.front();
				de.pop_front();

				// Add matched T
				st.update(j, -1);
			}

			// Add C
			st.update(l, +1);
		}
		
		for (const auto &query : queries_by_l[l]) {
			int r, q;
			tie(r, q) = query;

			int cnt_T_in_deque = distance(
				de.begin(),
				upper_bound(de.begin(), de.end(), r)
			);
			int cnt_T_in_left_seq = st.get(l, r).rems;

			// cerr << "[l, r] = [" << l << ", " << r << "]" << endl;
			// cerr << "cnt_T_in_deque = " << cnt_T_in_deque << endl;
			// cerr << "cnt_T_in_left_seq = " << cnt_T_in_left_seq << endl;

			ans[q] = cnt_T_in_deque + cnt_T_in_left_seq;
		}
	}

	for (int q = 0; q < Q; q++)
		cout << ans[q] << '\n';
}
	
int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	init();
	solve();

	return 0;
}

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29532 KB Output is correct
2 Correct 8 ms 29532 KB Output is correct
3 Correct 8 ms 29532 KB Output is correct
4 Correct 8 ms 29604 KB Output is correct
5 Correct 8 ms 29532 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29532 KB Output is correct
2 Correct 8 ms 29532 KB Output is correct
3 Correct 8 ms 29532 KB Output is correct
4 Correct 8 ms 29604 KB Output is correct
5 Correct 8 ms 29532 KB Output is correct
6 Correct 53 ms 32480 KB Output is correct
7 Correct 53 ms 32120 KB Output is correct
8 Correct 47 ms 32084 KB Output is correct
9 Correct 48 ms 32344 KB Output is correct
10 Correct 50 ms 32336 KB Output is correct
11 Correct 55 ms 32592 KB Output is correct
12 Correct 53 ms 32596 KB Output is correct
13 Correct 56 ms 32592 KB Output is correct
14 Correct 52 ms 32596 KB Output is correct
15 Correct 50 ms 32340 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 29532 KB Output is correct
2 Correct 8 ms 29532 KB Output is correct
3 Correct 8 ms 29532 KB Output is correct
4 Correct 8 ms 29604 KB Output is correct
5 Correct 8 ms 29532 KB Output is correct
6 Correct 53 ms 32480 KB Output is correct
7 Correct 53 ms 32120 KB Output is correct
8 Correct 47 ms 32084 KB Output is correct
9 Correct 48 ms 32344 KB Output is correct
10 Correct 50 ms 32336 KB Output is correct
11 Correct 55 ms 32592 KB Output is correct
12 Correct 53 ms 32596 KB Output is correct
13 Correct 56 ms 32592 KB Output is correct
14 Correct 52 ms 32596 KB Output is correct
15 Correct 50 ms 32340 KB Output is correct
16 Correct 459 ms 50596 KB Output is correct
17 Correct 322 ms 46424 KB Output is correct
18 Correct 387 ms 47444 KB Output is correct
19 Correct 374 ms 48984 KB Output is correct
20 Correct 430 ms 49584 KB Output is correct
21 Correct 499 ms 51796 KB Output is correct
22 Correct 458 ms 51280 KB Output is correct
23 Correct 489 ms 52052 KB Output is correct
24 Correct 460 ms 51392 KB Output is correct
25 Correct 445 ms 50924 KB Output is correct