Submission #380612

#	Time	Username	Problem	Language	Result	Execution time	Memory
380612		VodkaInTheJar	Election (BOI18_election)	C++14	100 / 100	1915 ms	198908 KiB

election

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'

using namespace std;

const int maxn = 5e5 + 3; 

int n, q; 
string s;

void read()
{
	cin >> n >> s >> q; 
}

struct node
{
	int to_delete, sum, min_suffix;
	node() {to_delete = sum = min_suffix = 0;}
	node(int to_delete, int sum, int min_suffix)
	{
		this->to_delete = to_delete;
		this->sum = sum;
		this->min_suffix = min_suffix;
	}
};

vector <node> tr[maxn * 4];
void build(int v, int l, int r)
{
	if (l == r)
	{
		tr[v].resize(2);
		if (s[l-1] == 'C')
		{
			tr[v][0] = node(0, 1, 0);
			tr[v][1] = node(0, 1, 0);
		}	
		
		else 
		{
			tr[v][0] = node(1, 0, 0);
			tr[v][1] = node(0, -1, -1);
		}
		
		return;
	}
	
	int mid = (l + r) / 2;
	build(v * 2, l, mid);
	build(v * 2 + 1, mid + 1, r);
	
	int len = r - l + 1; 
	tr[v].resize(len + 1);
	for (int i = 0; i <= len; i++)
	{
		auto first = tr[v * 2][min(i, (int)tr[v * 2].size()-1)];
		tr[v][i].to_delete += first.to_delete;
		
		auto second = tr[v * 2 + 1][min(i + first.sum, (int)tr[v * 2 + 1].size()-1)];
		tr[v][i].to_delete += second.to_delete;
		tr[v][i].sum = first.sum + second.sum;
		tr[v][i].min_suffix = min(second.min_suffix, second.sum + first.min_suffix);
		
		//~ if (l == 4 && r == 5)
		//~ if (i == 0)
		//~ cout << l << " " << r << " " << tr[v][i].to_delete << " " << tr[v][i].sum << " " << tr[v][i].min_suffix << endl;
	}
}

vector <int> curr;
void get(int v, int l, int r, int ll, int rr)
{
	if (l > rr || r < ll)
	return;
	
	if (l >= ll && r <= rr)
	{
		curr.push_back(v);
		return;
	}
	
	int mid = (l + r) / 2;
	get (v * 2, l, mid, ll, rr);
	get (v * 2 + 1, mid + 1, r, ll, rr);
}

void solve()
{
	build(1, 1, n);

	while (q--)
	{
		int l, r;
		cin >> l >> r; 
		
		curr.clear();
		get(1, 1, n, l, r);
		
		int ans = 0;
		int balance = 0;
		vector <pair <int, int> > v; 
		
		for (auto i: curr)
		{
			auto temp = tr[i][min((int)tr[i].size()-1, balance)];
			ans += temp.to_delete;
			balance += temp.sum;
			
			v.push_back({temp.sum, temp.min_suffix});
		}
		
		balance = 0;
		int to_add = 0;
		for (int i = (int)v.size() - 1; i >= 0; i--)
		{
			to_add = min(to_add, balance + v[i].second);
			balance += v[i].first;
		}
		
		cout << ans - to_add << endl; 
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	read();
	solve();
}

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