Submission #705285

#	Time	Username	Problem	Language	Result	Execution time	Memory
705285		penguinhacker	Election (BOI18_election)	C++17	100 / 100	561 ms	43660 KiB

election

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=5e5;
int n, q, ans[mxN];
string s;
ar<int, 2> st[1<<20];
vector<ar<int, 2>> queries[mxN];
vector<int> stk;

ar<int, 2> cmb(ar<int, 2> a, ar<int, 2> b) {
	return {a[0]+b[0], min(a[1], a[0]+b[1])};
}

void upd(int i, int x, int u=1, int l=0, int r=n-1) {
	if (l==r) {
		st[u][0]=x;
		st[u][1]=min(0, st[u][0]);
		return;
	}
	int mid=(l+r)/2;
	i<=mid?upd(i, x, 2*u, l, mid):upd(i, x, 2*u+1, mid+1, r);
	st[u]=cmb(st[2*u], st[2*u+1]);
}

ar<int, 2> qry(int ql, int qr, int u=1, int l=0, int r=n-1) {
	if (l>qr||r<ql)
		return {};
	if (ql<=l&&r<=qr)
		return st[u];
	int mid=(l+r)/2;
	return cmb(qry(ql, qr, 2*u, l, mid), qry(ql, qr, 2*u+1, mid+1, r));
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> s >> q;
	for (int i=0; i<q; ++i) {
		int l, r;
		cin >> l >> r, --l, --r;
		queries[r].push_back({l, i});
	}
	for (int i=0; i<n; ++i) {
		if (s[i]=='C') {
			upd(i, 1);
			if (stk.size()) {
				upd(stk.back(), -1);
				stk.pop_back();
			}
		} else {
			upd(i, 0);
			stk.push_back(i);
		}
		for (auto [l, ind] : queries[i]) {
			int x=stk.end()-lower_bound(stk.begin(), stk.end(), l);
			ans[ind]=x-qry(l, i)[1];
		}
	}
	for (int i=0; i<q; ++i)
		cout << ans[i] << "\n";
	return 0;
}

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