Submission #71543

#	Time	Username	Problem	Language	Result	Execution time	Memory
71543		aome	Election (BOI18_election)	C++17	100 / 100	551 ms	105636 KiB

election

#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 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18