| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 239414 |
2020-06-15T14:06:02 Z |
MrRobot_28 |
Krov (COCI17_krov) |
C++17 |
|
1500 ms |
15148 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);
l = r;
t1 = calc_left(root1, x[i] + l - i);
t2 = calc_left(root2, x[i] + l + i);
t3 = calc_right(root1, x[i] + l - i);
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);
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):
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
512 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
512 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
640 KB |
Output is correct |
| 2 |
Incorrect |
17 ms |
768 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
1152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
242 ms |
4216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
394 ms |
5992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
428 ms |
5816 KB |
Output is correct |
| 2 |
Incorrect |
637 ms |
12924 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1593 ms |
15148 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
