This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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> V;
const ll INF = 1e10;
ll Idx1(ll k){
return lower_bound(V.begin(), V.end(), k) - V.begin();
}
ll Idx2(ll k){
return upper_bound(V.begin(), V.end(), k) - V.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(Idx1(-INF), Idx2(K)) - sfs.query(Idx1(-INF), Idx2(K));
r += sfs.query(Idx1(K + 1), Idx2(INF)) - K * sfc.query(Idx1(K + 1), Idx2(INF));
return r;
}
int main(){
cin.tie(0) -> sync_with_stdio(false);
V.push_back(-INF - 1);
V.push_back(-INF);
V.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;
V.push_back(A[i]); V.push_back(B[i]); V.push_back(C[i]);
}
sort(V.begin(), V.end());
V.erase(unique(V.begin(), V.end()), V.end());
ll ans = 1e18;
for(ll i = 1; i <= N; i++){
sfs.update(Idx1(B[i]), B[i]);
sfc.update(Idx1(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(Idx1(B[i]), -B[i]);
sfc.update(Idx1(B[i]), -1);
ll L = 0, R = 1e12;
while(R - L > 3){
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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |