fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long lint;
  4. const int MAXN = 100005;
  5. const int mod = 1e9 + 7;
  6. typedef pair<int, int> pi;
  7.  
  8. int n, a[MAXN];
  9. vector<int> l, r;
  10.  
  11. struct bit{
  12.     int tree[MAXN];
  13.     void add(int x, int v){
  14.         x++;
  15.         while(x <= n){
  16.             tree[x] += v;
  17.             x += x & -x;
  18.         }
  19.     }
  20.     int sum(int x){
  21.         x++;
  22.         int ret = 0;
  23.         while(x){
  24.             ret += tree[x];
  25.             x -= x & -x;
  26.         }
  27.         return ret;
  28.     }
  29. }bl, br;
  30.  
  31. struct bit2{
  32.     lint tree[MAXN];
  33.     void add(int x, lint v){
  34.         x++;
  35.         while(x <= n){
  36.             tree[x] += v;
  37.             x += x & -x;
  38.         }
  39.     }
  40.     lint sum(int x){
  41.         x++;
  42.         lint ret = 0;
  43.         while(x){
  44.             ret += tree[x];
  45.             x -= x & -x;
  46.         }
  47.         return ret;
  48.     }
  49. }ql, qr;
  50.  
  51. int it1, it2;
  52.  
  53. int trial(int i, int x){
  54.     int ans = 0;
  55.     it1 = upper_bound(l.begin(), l.end(), x - i) - l.begin();
  56.     ans += bl.sum(it1 - 1);
  57.     it2 = upper_bound(r.begin(), r.end(), x + i) - r.begin();
  58.     ans += br.sum(it2 - 1);
  59.     return ans;
  60. }
  61.  
  62. lint solve(int i, int x){
  63.     lint ans = 0;
  64.     ans += (x - i) * bl.sum(it1 - 1) - ql.sum(it1 - 1);
  65.     ans += (ql.sum(n-1) - ql.sum(it1 - 1)) - (x - i) * (bl.sum(n-1) - bl.sum(it1 - 1));
  66.     ans += (x + i) * br.sum(it2 - 1) - qr.sum(it2 - 1);
  67.     ans += (qr.sum(n-1) - qr.sum(it2 - 1)) - (x + i) * (br.sum(n-1) - br.sum(it2 - 1));
  68.     return ans;
  69. }
  70.  
  71. int main(){
  72.     scanf("%d",&n);
  73.     for(int i=1; i<=n; i++){
  74.         scanf("%d",&a[i]);
  75.     }
  76.     for(int i=1; i<=n; i++){
  77.         l.push_back(a[i] - i);
  78.         r.push_back(a[i] + i);
  79.     }
  80.     sort(l.begin(), l.end());
  81.     sort(r.begin(), r.end());
  82.     l.resize(unique(l.begin(), l.end()) - l.begin());
  83.     r.resize(unique(r.begin(), r.end()) - r.begin());
  84.     for(int i=1; i<=n; i++){
  85.         auto pr = lower_bound(r.begin(), r.end(), a[i] + i) - r.begin();
  86.         br.add(pr, 1);
  87.         qr.add(pr, a[i] + i);
  88.     }
  89.     lint ans = 1e18;
  90.     for(int i=1; i<=n; i++){
  91.         auto pl = lower_bound(l.begin(), l.end(), a[i] - i) - l.begin();
  92.         auto pr = lower_bound(r.begin(), r.end(), a[i] + i) - r.begin();
  93.         bl.add(pl, 1);
  94.         br.add(pr, -1);
  95.         ql.add(pl, (a[i] - i));
  96.         qr.add(pr, -(a[i] + i));
  97.         int s = max(i, n + 1 - i), e = 1e9 + 1e6;
  98.         while(s != e){
  99.             int m = (s+e)/2;
  100.             if(trial(i, m) >= (n+1)/2) e = m;
  101.             else s = m+1;
  102.         }
  103.         ans = min(ans, solve(i, s));
  104.     }
  105.     cout << ans << endl;
  106. }
Success #stdin #stdout 0s 4252KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000000000000
https://ideone.com/5tyUj0
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!