Submission #239423

#	Time	Username	Problem	Language	Result	Execution time	Memory
239423		MrRobot_28	Krov (COCI17_krov)	C++17	140 / 140	1283 ms	17348 KiB

krov

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node{
	node* left;
	node* right;
	int suma, sum, a, priority, cnt, cnt1;
	node(int a, int priority):
		a(a),
		sum(a),
		suma(a),
		cnt(1),
		cnt1(1),
		left(0),
		right(0),
		priority(priority){};
};
void relax(node* &v)
{
	v -> suma = v -> a * v -> cnt1;
	v -> sum = v -> suma;
	v -> cnt = v -> cnt1;
	if(!v -> left)
	{
		
	}
	else
	{
		v -> sum += v -> left -> sum;
		v -> cnt += v -> left -> cnt;
	}
	if(!v -> right)
	{
		
	}
	else
	{
		v -> sum += v -> right -> sum;
		v -> cnt += v -> right -> cnt;
	}
}
bool increase(node* &v, int a)
{
	if(!v)
	{
		return false;
	}
	if(v -> a == a)
	{
		v -> cnt1++;
		relax(v);
		return true;
	}
	bool fl;
	if(v -> a > a)
	{
		fl = increase(v -> left, a);
	}
	else
	{
		fl = increase(v -> right, a);
	}
	relax(v);
	return fl;
}
bool decrease(node* &v, int a)
{
	if(v -> a == a)
	{
		v -> cnt1--;
		relax(v);
		return v -> cnt1 == 0;
	}
	bool fl;
	if(v -> a > a)
	{
		fl = decrease(v -> left, a);
	}
	else
	{
		fl = decrease(v -> right, a);
	}
	relax(v);
	return fl;
}
void split(node* v, node* &left, node* &right, int a)
{
	if(!v)
	{
		left = right = NULL;
		return;
	}
	if(v -> a == a)
	{
		left = v -> left;
		right = v -> right;
		return;
	}
	if(v -> a < a)
	{
		split(v -> right, v -> right, right, a);
		left = v;
		relax(left);
	}
	else
	{
		split(v -> left, left, v -> left, a);
		right = v;
		relax(right);
	}
}
node* merge(node* l, node* r)
{
	if(!l)
	{
		return r;
	}
	else if(!r)
	{
		return l;
	}
	if(r -> priority < l -> priority)
	{
		r -> left = merge(l, r -> left);
		relax(r);
		return r;
	}
	else
	{
		l -> right = merge(l -> right, r);
		relax(l);
		return l;
	}
}
pair <int, int> calc_left(node* v, int a)
{
	if(!v)
	{
		return {0, 0};
	}
	if(v -> a > a)
	{
		return calc_left(v -> left, a);
	}
	pair <int, int> t1 = {0, 0};
	if(!v -> left)
	{
		
	}
	else
	{
		t1.first = v -> left -> sum;
		t1.second = v -> left -> cnt;
	}
	t1.first += v -> suma;
	t1.second += v -> cnt1;
	swap(t1.first, t1.second);
	pair <int, int> t2 = calc_left(v -> right, a);
	return {t1.first + t2.first, t1.second + t2.second};
}
pair <int, int> calc_right(node* v, int a)
{
	if(!v)
	{
		return {0, 0};
	}
	if(v -> a <= a)
	{
		return calc_right(v -> right, a);
	}
	pair <int, int> t1 = {0, 0};
	if(!v -> right)
	{
		
	}
	else
	{
		t1.first += v -> right -> sum;
		t1.second += v -> right -> cnt;
	}
	t1.first += v -> suma;
	t1.second += v -> cnt1;
	swap(t1.first, t1.second);
	pair <int, int> t2 = calc_right(v -> left, a);
	return {t1.first + t2.first, t1.second + t2.second};
}
void add(node* &v, int a)
{
	if(increase(v, a))
	{
		return;
	}
	node* L;
	node* R;
	split(v, L, R, a);
	node* v1 = new node(a, rand());
	L = merge(L, v1);
	v = merge(L, R);
}
void erase(node* &v, int a)
{
	if(!decrease(v, a)){
		return;
	}
	node* L;
	node* R;
	split(v , L, R, a);
	v = merge(L, R);
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	vector <int> x(n);
	for(int i = 0; i < n; i++)
	{
		cin >> x[i];
	}
	node* root1;
	node* root2;
	root1 = root2 = NULL;
	for(int i = 0; i < n; i++)
	{
		add(root2, i + x[i]);
	}
	int ans = 1e18;
	for(int i = 0; i < n; i++)
	{
		int l = i + 1, r = 2e9;
		if( l < n - i)
		{
			l = n - i;
		}
		while(r - l > 1)
		{
			int midd = (r + l) / 2;
			int cnt1 = calc_left(root1, midd - i).first + calc_left(root2, midd + i).first;
			if(cnt1 * 2 <= n)
			{
				l = midd;
			}
			else
			{
				r = midd;
			}
		}
		pair <int, int> t1 = calc_left(root1, l - i);
		pair <int, int> t2 = calc_left(root2, l + i);
		pair <int, int> t3 = calc_right(root1,  l - i);
		pair <int, int> t4 = calc_right(root2, l + i);
		ans = min(ans, t1.first * (l - i) - t1.second + t2.first * ( l + i) - t2.second
		+ t3.second - (l - i) * t3.first + t4.second - (l + i) * t4.first);
		l = r;
		t1 = calc_left(root1, l - i);
		t2 = calc_left(root2, l + i);
		t3 = calc_right(root1, l - i);
		t4 = calc_right(root2, l + i);
		ans = min(ans, t1.first * (l - i) - t1.second + t2.first * (l + i) - t2.second
		+ t3.second - (l - i) * t3.first + t4.second - (l + i) * t4.first);
		l = r;
		erase(root2, x[i] + i);
		add(root1, x[i] - i);
	}
	cout << ans;
    return 0;
}

Compilation message (stderr)

krov.cpp: In constructor 'node::node(long long int, long long int)':
krov.cpp:7:17: warning: 'node::a' will be initialized after [-Wreorder]
  int suma, sum, a, priority, cnt, cnt1;
                 ^
krov.cpp:7:12: warning:   'long long int node::sum' [-Wreorder]
  int suma, sum, a, priority, cnt, cnt1;
            ^~~
krov.cpp:8:2: warning:   when initialized here [-Wreorder]
  node(int a, int priority):
  ^~~~
krov.cpp:7:12: warning: 'node::sum' will be initialized after [-Wreorder]
  int suma, sum, a, priority, cnt, cnt1;
            ^~~
krov.cpp:7:6: warning:   'long long int node::suma' [-Wreorder]
  int suma, sum, a, priority, cnt, cnt1;
      ^~~~
krov.cpp:8:2: warning:   when initialized here [-Wreorder]
  node(int a, int priority):
  ^~~~
krov.cpp:7:35: warning: 'node::cnt1' will be initialized after [-Wreorder]
  int suma, sum, a, priority, cnt, cnt1;
                                   ^~~~
krov.cpp:5:8: warning:   'node* node::left' [-Wreorder]
  node* left;
        ^~~~
krov.cpp:8:2: warning:   when initialized here [-Wreorder]
  node(int a, int priority):
  ^~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14