Submission #380586

#	Time	Username	Problem	Language	Result	Execution time	Memory
380586		VodkaInTheJar	Election (BOI18_election)	C++14	0 / 100	37 ms	47724 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() {}
	node(int to_delete, int sum, int min_suffix)
	{
		this->to_delete = to_delete;
		this->sum = sum;
		this->min_suffix = min_suffix;
	}
};

int get_min(vector <pair <int, int> > &v)
{
	int ans = 0;
	for (auto i: v)
	ans = min(ans, i.second);
    
    return ans;
}

vector <node> tr[maxn * 4];
void build(int v, int l, int r)
{
	int len = r - l + 1; 
	tr[v].resize(len + 1);
	
	vector <pair <int, int> > st; 
	st.push_back({r + 1, 0});
	
	int balance = 0;
	for (int i = r; i >= l; i--)
	{
		if (s[i-1] == 'C')
		balance++;
		
		else 
		balance--;
		
		if (balance < st.back().second)
		st.push_back({i, balance});
	}
	
	reverse (st.begin(), st.end());
	
	vector <int> f(len + 1, -1);
	balance = 0;
	for (int i = l; i <= r; i++)
	{
		if (s[i-1] == 'C')
		balance++;
		
		else 
		balance--;
		
		for (int j = -balance-1; j >= 0; j--)
		if (f[j] == -1)
		f[j] = i;
	}
	
	int curr_del = 0;
	for (int i = len; i >= 0; i--)
	{
		if (f[i] != -1 && f[i] != f[i+1])
		{
			for (auto &j: st)
		    if (j.first <= f[i])
		    j.second++;
		    
		    curr_del++;
	        balance++;
	    }
		
		tr[v][i] = node(curr_del, balance, get_min(st));
	}
	
	if (l == r)
	return;
	
	int mid = (l + r) / 2;
	build(v * 2, l, mid);
	build(v * 2 + 1, mid + 1, r);
}

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(), 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: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18