Submission #281526

#	Time	Username	Problem	Language	Result	Execution time	Memory
281526		Atalasion	Election (BOI18_election)	C++14	0 / 100	2 ms	512 KiB

election

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 500000 + 10;
const int MOD = 1000000007;
const int LOG = 20;
const int INF = 1000000010;
const int delta = 11353;

struct node{
	int mn, mx, Rmx, Lmn;
};

node seg[N << 2];
int n, q, ps[N], ted[N];
string s;

node merge(node x, node y){
	node res = x;
	res.mx = y.mx, res.Rmx = y.Rmx;
	if (res.mn > y.mn) res.mn = y.mn, res.Lmn = y.Lmn;
	if (x.mx > res.mx) res.mx = x.mx, res.Rmx = x.Rmx;
	return res;
}

void build(int id, int l, int r){
	if (r - l == 1){
		seg[id].mn = seg[id].mx = ps[l], seg[id].Rmx = seg[id].Lmn = l;
		return;
	}
	int md = (l + r) >> 1;
	build(id << 1, l, md);
	build(id << 1 | 1, md, r);
	seg[id] = merge(seg[id << 1], seg[id << 1 | 1]);
}

node get(int id, int lq, int rq, int l, int r){
	if (rq <= l || r <= lq){
		node res;
		res.mx = -INF, res.mn = INF;
		return res;
	}
	if (lq <= l && r <= rq) return seg[id];
	int md = (l + r) >> 1;
	return merge(get(id << 1, lq, rq, l, md), get(id << 1 | 1, lq, rq, md, r));
}

int SZ(int L, int R, int LL, int RR){
	int l = max(L, LL), r = min(R, RR);
	if(r < l) return 0;
	return ted[r] - ted[l - 1];
}

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> s;
	for (int i = 1; i <= n; i++){
		ted[i] = ted[i - 1];
		if (s[i - 1] == 'C') ps[i] = ps[i - 1] + 1;
		else ps[i] = ps[i - 1] - 1, ted[i]++;
	}
	build(1, 1, n + 1);
	cin >> q;
	//cout <<seg[1].mx << ' ' << seg[1].mn << '\n';
	for (int i = 0; i < q; i++){
		int l, r;
		cin >> l >> r;
		node res = get(1, l - 1, r + 1, 1, n + 1);
		int L, R;
		int ans = 0;
		if (res.mx <= ps[r]) L = n + 1, R = n + 1;
		else L = res.Rmx + 1, R = r;
		//ans += res.mx - ps[r];
		int LL, RR;
		if (res.mn >= ps[l - 1]) LL = 0, RR = 0;
		else LL = l, RR = res.Lmn;
		//ans += ps[l - 1] - res.mn;
		//cout << ans << '\n';
		//cout << L << ' ' << R << ' ' << LL << ' ' << RR << '\n';
		int x = SZ(L, R, LL, RR);
		//cout << x << '\n';
		int val1 = res.mx - ps[r], val2 = ps[l - 1] - res.mn;
		ans += min({val1, val2, x});
		ans += (val1 - ans) + (val2 - ans);
		cout << ans << '\n';
	}
	return 0;
}

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