Submission #941433

#	Time	Username	Problem	Language	Result	Execution time	Memory
941433		freedommo33	Election (BOI18_election)	C++17	0 / 100	5 ms	12636 KiB

election

#include <bits/stdc++.h>

using namespace std;
constexpr int M = 500'005;
constexpr int base = 500'005;
pair<int, int> tree[2][base*2]; //od przodu, od tyłu
int lewo[M];
int prawo[M];

pair<int, int> query(int a, int b, int v2){
	a = a + base - 1;
	b = b + base + 1;
	pair<int, int> wynik = {21376969, 0};
	while(a/2!=b/2){
		if(a%2==0 && wynik.first >= tree[v2][a+1].first) wynik = tree[v2][a+1];
		if(b%2==1 && wynik.first >= tree[v2][b-1].first) wynik = tree[v2][b-1];
		a/=2, b/=2;
	}
	return wynik;
}
void add(int v, int x, int v2){
	tree[v2][v + base].second = v;
	v = v + base;
	tree[v2][v].first += x;
	v/=2; 
	while(v){
		if(tree[v2][v*2].first < tree[v2][v*2+1].first) tree[v2][v] = tree[v2][v*2];
		else	tree[v2][v] = tree[v2][v*2+1];
		v/=2;
	}
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin>>n;
	string s;
	cin>>s;
	for(int i=1; i<=n; i++){
		lewo[i] = lewo[i-1];
		if(s[i-1]=='C') lewo[i]++;
		else		lewo[i]--;
	}
	for(int i=n; i>=1; i--){
		prawo[i] = prawo[i+1];
		if(s[i-1]=='C') prawo[i]++;
		else		prawo[i]--;
	}
	for(int i=1; i<=n; i++){
		add(i, lewo[i], 0);
		add(i, prawo[i], 1);
	}
	//for(int i=1; i<=n; i++) cout<<lewo[i]<<" ";
	//cout<<endl;
	//for(int i=1; i<=n; i++) cout<<prawo[i]<<" ";
	//cout<<endl;
	//cout<<endl;
	int k;
	cin>>k;
	while(k--){
		int a, b;
		cin>>a>>b;
		int odPrawej = prawo[b];
		int odLewej = lewo[a];
		if(s[b-1]=='C') odPrawej = odPrawej - 1;
		else		odPrawej = odPrawej + 1;
		if(s[a-1]=='C') odLewej = odLewej - 1;
		else		odLewej = odLewej + 1;
		
		//cout<<odLewej<<" "<<odPrawej<<endl;
		pair<int, int> minLewo = query(a, b, 0);
		minLewo.first -= odLewej;
		//cout<<minLewo.first<<" "<<minLewo.second<<endl;
		pair<int, int> minPrawo1 = query(a, minLewo.second, 1);
		pair<int, int> minPrawo2 = query(minLewo.second+1, b, 1);
		pair<int, int> minPrawo;
		minLewo.first = min(0, minLewo.first);
		if(minPrawo1.first + minLewo.first*-1 < minPrawo2.first) minPrawo.first = minPrawo1.first + minLewo.first*-1;
		else	minPrawo = minPrawo2;
		//cout<<minPrawo1.first<<" "<<minPrawo1.second<<endl;
		//cout<<minPrawo2.first<<" "<<minPrawo2.second<<endl;
		minPrawo.first -= odPrawej;
		minPrawo.first = min(0, minPrawo.first);
		cout<<minLewo.first*-1 + minPrawo.first*-1<<endl;
		//cout<<endl; 
	}
	return 0;
}

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