#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll N;
ll A[100005];
ll B[100005];
ll C[100005];
struct BIT{
ll T[300015] = {};
void update(ll k, ll v){while(k <= 300010) T[k] += v, k += k & -k;}
ll sum(ll k){ll r = 0;while(k >= 1) r += T[k], k -= k & -k; return r;}
ll query(ll l, ll r) {return sum(r) - sum(l - 1);}
};
BIT pfs, pfc, sfs, sfc;
vector<ll> V1;
const ll INF = 1e10;
ll Idx1(ll k){
return lower_bound(V1.begin(), V1.end(), k) - V1.begin();
}
ll Idx2(ll k){
return upper_bound(V1.begin(), V1.end(), k) - V1.begin() - 1;
}
ll Idx3(ll k){
return lower_bound(V2.begin(), V2.end(), k) - V2.begin();
}
ll Idx4(ll k){
return upper_bound(V2.begin(), V2.end(), k) - V2.begin() - 1;
}
ll f(ll X, ll K){
ll r = 0;
K -= X;
r += K * pfc.query(Idx1(-INF), Idx2(K)) - pfs.query(Idx1(-INF), Idx2(K));
r += pfs.query(Idx1(K + 1), Idx2(INF)) - K * pfc.query(Idx1(K + 1), Idx2(INF));
K += 2 * X;
r += K * sfc.query(Idx3(-INF), Idx4(K)) - sfs.query(Idx3(-INF), Idx4(K));
r += sfs.query(Idx3(K + 1), Idx4(INF)) - K * sfc.query(Idx3(K + 1), Idx4(INF));
return r;
}
int main(){
cin.tie(0) -> sync_with_stdio(false);
V1.push_back(-INF - 1);
V1.push_back(-INF);
V1.push_back(INF);
cin >> N;
for(ll i = 1; i <= N; i++){
cin >> A[i];
B[i] = A[i] + i;
C[i] = A[i] - i;
V1.push_back(A[i]); V1.push_back(B[i]);
V2.push_back(A[i]); V2.push_back(B[i]);
}
sort(V1.begin(), V1.end());
V1.erase(unique(V1.begin(), V1.end()), V1.end());
sort(V2.begin(), V2.end());
V2.erase(unique(V2.begin(), V2.end()), V2.end());
ll ans = 1e18;
for(ll i = 1; i <= N; i++){
sfs.update(Idx3(B[i]), B[i]);
sfc.update(Idx3(B[i]), 1);
}
for(ll i = 1; i <= N; i++){
pfs.update(Idx1(C[i]), C[i]);
pfc.update(Idx1(C[i]), 1);
sfs.update(Idx4(B[i]), -B[i]);
sfc.update(Idx4(B[i]), -1);
ll L = 0, R = 1e10;
while(R - L > 20){
ll p = (L * 2 + R) / 3, q = (L + R * 2) / 3;
if(f(i, p) <= f(i, q)) R = q;
else L = p;
}
L = max(L, i);
L = max(L, N + 1 - i);
for(ll j = L; j <= R; j++){
ans = min(ans, f(i, j));
}
}
cout << ans;
}
Compilation message
krov.cpp: In function 'll Idx3(ll)':
krov.cpp:25:24: error: 'V2' was not declared in this scope; did you mean 'V1'?
25 | return lower_bound(V2.begin(), V2.end(), k) - V2.begin();
| ^~
| V1
krov.cpp: In function 'll Idx4(ll)':
krov.cpp:28:24: error: 'V2' was not declared in this scope; did you mean 'V1'?
28 | return upper_bound(V2.begin(), V2.end(), k) - V2.begin() - 1;
| ^~
| V1
krov.cpp: In function 'int main()':
krov.cpp:55:9: error: 'V2' was not declared in this scope; did you mean 'V1'?
55 | V2.push_back(A[i]); V2.push_back(B[i]);
| ^~
| V1
krov.cpp:59:10: error: 'V2' was not declared in this scope; did you mean 'V1'?
59 | sort(V2.begin(), V2.end());
| ^~
| V1
