Submission #107367

#	Time	Username	Problem	Language	Result	Execution time	Memory
107367		Saboon	Election (BOI18_election)	C++14	100 / 100	1950 ms	38260 KiB

election

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 5e5 + 10;

struct node{
	int compT;
	int lefT;
	int rigT;
	int remT;
	int frelefC;
	int frerigC;
	
	void merge(node oth){
		int tmp = min(frerigC, oth.lefT);
		compT += tmp;
		frerigC -= tmp;
		oth.lefT -= tmp;
		
		tmp = min(rigT, oth.frelefC);
		compT += tmp;
		rigT -= tmp;
		oth.frelefC -= tmp;
	
		tmp = min(remT, oth.frelefC);
		lefT += tmp;
		remT -= tmp;
		oth.frelefC -= tmp;

		tmp = min(frerigC, oth.remT);
		rigT += tmp;
		frerigC -= tmp;
		oth.remT -= tmp;

		tmp = min(rigT, oth.lefT);
		compT += tmp;
		rigT -= tmp;
		oth.lefT -= tmp;
		remT += tmp;

		compT += oth.compT;
		lefT += oth.lefT;
		rigT += oth.rigT;
		remT += oth.remT;
		frelefC += oth.frelefC;
		frerigC += oth.frerigC;
	}

	void debug(){
		cout << "complete T : " << compT << endl;
		cout << "left C need for T : " << lefT << endl;
		cout << "right C need for T : " << rigT << endl;
		cout << "empty T : " << remT << endl;
		cout << "Free left C's " << frelefC << endl;
		cout << "Free Right C's " << frerigC << endl;
	}
};

node seg[4 * maxn];

string s;

node get(int id, int L, int R, int l, int r){
	if (L == l and R == r)
		return seg[id];
	int mid = (L + R) >> 1;
	if (mid >= r)
		return get(2 * id + 0, L, mid, l, r);
	if (mid <= l)
		return get(2 * id + 1, mid, R, l, r);
	node me = get(2 * id + 0, L, mid, l, mid);
	me.merge(get(2 * id + 1, mid, R, mid, r));
	return me;
}

void build(int id, int L, int R){
	if (L + 1 == R){
		if (s[L] == 'T')
			seg[id].remT ++;
		else
			seg[id].frelefC = seg[id].frerigC = 1;
		return;
	}
	int mid = (L + R) >> 1;
	build(2 * id + 0, L, mid);
	build(2 * id + 1, mid, R);
	seg[id] = seg[2 * id + 0];
	seg[id].merge(seg[2 * id + 1]);
//	cout << "################printing : " << L << " " << R << endl;
//	seg[id].debug();
}

int par[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	cin >> s;
	build(1, 0, n);
	for (int i = 0; i < n; i++)
		par[i] = (s[i] == 'C') + (i > 0 ? par[i - 1] : 0);
	int m;
	cin >> m;
	for (int i = 0; i < m; i++){
		int l, r;
		cin >> l >> r;
		l --, r --;
		int rem = par[r] - (l > 0 ? par[l - 1] : 0) + get(1, 0, n, l, r + 1).compT;
		cout << (r - l + 1) - rem << '\n';
	}
}

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