Submission #918847

#	Time	Username	Problem	Language	Result	Execution time	Memory
918847		myst6	Election (BOI18_election)	C++17	0 / 100	2 ms	600 KiB

election

#include <bits/stdc++.h>

using namespace std;

struct Tree {
	vector<int> info, tags;
	Tree(int size) {
		info.resize(size*4, 0);
		tags.resize(size*4);
	}
	void pushdown(int x) {
		info[x] += tags[x];
		if (x*2 < tags.size()) tags[x*2] += tags[x];
		if (x*2+1 < tags.size()) tags[x*2+1] += tags[x];
		tags[x] = 0;
	}
	void update(int l, int r, int x, int xl, int xr, int tag) {
		if (l > r) return;
		if (l == xl && r == xr) {
			tags[x] += tag;
		} else {
			int xm = (xl+xr)/2;
			update(l, min(r,xm), x*2, xl, xm, tag);
			update(max(l,xm+1), r, x*2+1, xm+1, xr, tag);
			pushdown(x*2); pushdown(x*2+1);
			info[x] = min(info[x*2], info[x*2+1]);
		}
	}
	int query(int l, int r, int x, int xl, int xr) {
		if (l > r) return 1<<30;
		pushdown(x);
		if (l == xl && r == xr) {
			return info[x];
		} else {
			int xm = (xl+xr)/2;
			int left = query(l, min(r,xm), x*2, xl, xm);
			int right = query(max(l,xm+1), r, x*2+1, xm+1, xr);
			return min(left, right);
		}
	}
};

struct BIT {
	vector<int> data;
	BIT(int size) {
		data.resize(size+1);
	}
	void update(int x, int delta) {
		while (x < data.size()) {
			data[x] += delta;
			x += x & (-x);
		}
	}
	int query(int x) {
		int ans = 0;
		while (x > 0) {
			ans += data[x];
			x -= x & (-x);
		}
		return ans;
	}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int N;
	cin >> N;
	string s;
	cin >> s;
	int Q;
	cin >> Q;
	vector<pair<int,int>> queries(Q);
	for (int i=0; i<Q; i++) {
		int L, R;
		cin >> L >> R;
		queries[i] = {L-1, R-1};
	}
	vector<int> order(Q);
	iota(order.begin(), order.end(), 0);
	sort(order.begin(), order.end(), [&](int i, int j) -> bool {
		return queries[i].first > queries[j].first;
	});
	int L = N-1;
	set<int> Xs;
	BIT left(N);
	Tree right(N);
	vector<int> ans(N);
	for (int i=0; i<Q; i++) {
		pair<int,int> q = queries[order[i]];
		while (L >= q.first) {
			if (s[L] == 'C') {
				if (!Xs.empty()) {
					int idx = *Xs.begin();
					left.update(idx+1, -1);
					right.update(0, idx, 1, 0, N-1, -1);
					Xs.erase(idx);
				}
				right.update(0, L, 1, 0, N-1, +1);
			} else {
				Xs.insert(L);
				left.update(L+1, +1);
			}
			L -= 1;
		}
		int R = q.second;
		int base = left.query(R+1);
		int extra = right.query(L+1, R, 1, 0, N-1);
		int next = R == N-1 ? 0 : right.query(R+1, R+1, 1, 0, N-1);
		ans[order[i]] = base - min(0, extra - next);
	}
	for (int i=0; i<Q; i++) {
		cout << ans[i] << "\n";
	}
	return 0;
}

Compilation message (stderr)

election.cpp: In member function 'void Tree::pushdown(int)':
election.cpp:13:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |   if (x*2 < tags.size()) tags[x*2] += tags[x];
      |       ~~~~^~~~~~~~~~~~~
election.cpp:14:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   if (x*2+1 < tags.size()) tags[x*2+1] += tags[x];
      |       ~~~~~~^~~~~~~~~~~~~
election.cpp: In member function 'void BIT::update(int, int)':
election.cpp:49:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   while (x < data.size()) {
      |          ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18