oj.uz

Submission #239383

# Submission time Handle Problem Language Result Execution time Memory
239383 2020-06-15T13:01:43 Z MrRobot_28 Krov (COCI17_krov) C++17
0 / 140
 1500 ms 15068 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 = 0, r = 2e9;
		if(x[i] < i + 1)
		{
			l = i + 1 - x[i];
		}
		if(x[i] + l < n - i)
		{
			l += n - i - l - x[i];
		}
		while(r - l > 1)
		{
			int midd = (r + l) / 2;
			int cnt1 = calc_left(root1, x[i] + midd - i).first + calc_left(root2, x[i] + midd + i).first;
			if(cnt1 * 2 <= n)
			{
				l = midd;
			}
			else
			{
				r = midd;
			}
		}
		pair <int, int> t1 = calc_left(root1, x[i] + l - i);
		pair <int, int> t2 = calc_left(root2, x[i] + l + i);
		pair <int, int> t3 = calc_right(root1, x[i] + l - i);
		pair <int, int> t4 = calc_right(root2, x[i] + l + i);
		ans = min(ans, t1.first * (x[i] + l - i) - t1.second + t2.first * (x[i] + l + i) - t2.second
		+ t3.second - (x[i] + l - i) * t3.first + t4.second - (x[i] + l + i) * t4.first);
		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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 1112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 268 ms 4088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 374 ms 5876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 460 ms 5688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1597 ms 15068 KB Time limit exceeded
2 Halted 0 ms 0 KB -