oj.uz

Submission #380612

# Submission time Handle Problem Language Result Execution time Memory
380612 2021-03-22T12:48:04 Z VodkaInTheJar Election (BOI18_election) C++14
100 / 100
 1915 ms 198908 KB 
#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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47872 KB Output is correct
2 Correct 36 ms 47724 KB Output is correct
3 Correct 35 ms 47724 KB Output is correct
4 Correct 35 ms 47724 KB Output is correct
5 Correct 38 ms 47724 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47872 KB Output is correct
2 Correct 36 ms 47724 KB Output is correct
3 Correct 35 ms 47724 KB Output is correct
4 Correct 35 ms 47724 KB Output is correct
5 Correct 38 ms 47724 KB Output is correct
6 Correct 185 ms 65772 KB Output is correct
7 Correct 149 ms 65772 KB Output is correct
8 Correct 187 ms 65772 KB Output is correct
9 Correct 160 ms 65772 KB Output is correct
10 Correct 207 ms 65772 KB Output is correct
11 Correct 214 ms 66080 KB Output is correct
12 Correct 190 ms 66028 KB Output is correct
13 Correct 202 ms 66028 KB Output is correct
14 Correct 205 ms 66028 KB Output is correct
15 Correct 199 ms 65772 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 47872 KB Output is correct
2 Correct 36 ms 47724 KB Output is correct
3 Correct 35 ms 47724 KB Output is correct
4 Correct 35 ms 47724 KB Output is correct
5 Correct 38 ms 47724 KB Output is correct
6 Correct 185 ms 65772 KB Output is correct
7 Correct 149 ms 65772 KB Output is correct
8 Correct 187 ms 65772 KB Output is correct
9 Correct 160 ms 65772 KB Output is correct
10 Correct 207 ms 65772 KB Output is correct
11 Correct 214 ms 66080 KB Output is correct
12 Correct 190 ms 66028 KB Output is correct
13 Correct 202 ms 66028 KB Output is correct
14 Correct 205 ms 66028 KB Output is correct
15 Correct 199 ms 65772 KB Output is correct
16 Correct 1723 ms 197960 KB Output is correct
17 Correct 1468 ms 197372 KB Output is correct
18 Correct 1527 ms 197584 KB Output is correct
19 Correct 1269 ms 197212 KB Output is correct
20 Correct 1915 ms 196856 KB Output is correct
21 Correct 1717 ms 198640 KB Output is correct
22 Correct 1820 ms 198560 KB Output is correct
23 Correct 1742 ms 198908 KB Output is correct
24 Correct 1761 ms 198660 KB Output is correct
25 Correct 1834 ms 198324 KB Output is correct