oj.uz

Submission #239423

# Submission time Handle Problem Language Result Execution time Memory
239423 2020-06-15T14:33:17 Z MrRobot_28 Krov (COCI17_krov) C++17
140 / 140
 1283 ms 17348 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 512 KB Output is correct
2 Correct 9 ms 512 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Output is correct
2 Correct 9 ms 512 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 512 KB Output is correct
2 Correct 12 ms 640 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 640 KB Output is correct
2 Correct 14 ms 512 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 640 KB Output is correct
2 Correct 16 ms 744 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1152 KB Output is correct
2 Correct 21 ms 768 KB Output is correct
3 Correct 17 ms 768 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 4088 KB Output is correct
2 Correct 118 ms 2532 KB Output is correct
3 Correct 194 ms 4288 KB Output is correct
4 Correct 235 ms 5112 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 5916 KB Output is correct
2 Correct 397 ms 7224 KB Output is correct
3 Correct 320 ms 7132 KB Output is correct
4 Correct 286 ms 6776 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 421 ms 5624 KB Output is correct
2 Correct 636 ms 12152 KB Output is correct
3 Correct 272 ms 5856 KB Output is correct
4 Correct 644 ms 11640 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1283 ms 16888 KB Output is correct
2 Correct 823 ms 17348 KB Output is correct
3 Correct 654 ms 11780 KB Output is correct
4 Correct 882 ms 14864 KB Output is correct
5 Correct 191 ms 4728 KB Output is correct