fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. void sol(long long l,long long r,long long vl,long long vr,vector<long long> &a,vector<long long> &res){
  6.   if(vl==vr){
  7.     for(long long i=l;i<=r;i++){
  8.       res[i]=vl;
  9.     }
  10.     return;
  11.   }
  12.   if(l>r){return;}
  13.   if(l==r){
  14.     if(a[l]<vl){res[l]=vl;}
  15.     else if(a[l]>vr){res[l]=vr;}
  16.     else{res[l]=a[l];}
  17.     return;
  18.   }
  19.  
  20.   long long md=(vl+vr)/2;
  21.  
  22.   long long h,mh;
  23.   long long lp=-1,rp=-1;
  24.   h=0; mh=0;
  25.   for(long long i=l;i<=r;i++){
  26.     if(a[i]<md){h++;}
  27.     else{h--;}
  28.     if(mh<h){
  29.       mh=h;
  30.       lp=i;
  31.     }
  32.   }
  33.   h=0; mh=0;
  34.   for(long long i=r;i>=l;i--){
  35.     if(a[i]>md){h++;}
  36.     else{h--;}
  37.     if(mh<h){
  38.       mh=h;
  39.       rp=i;
  40.     }
  41.   }
  42.  
  43.   if(lp==-1){
  44.     lp=l;
  45.   }
  46.   else{
  47.     sol(l,lp,vl,md-1,a,res);
  48.     lp++;
  49.   }
  50.  
  51.   if(rp==-1){
  52.     rp=r;
  53.   }
  54.   else{
  55.     sol(rp,r,md+1,vr,a,res);
  56.     rp--;
  57.   }
  58.  
  59.   for(long long i=lp;i<=rp;i++){res[i]=md;}
  60.   return;
  61. }
  62.  
  63. int main(){
  64.   ios::sync_with_stdio(false);
  65.   cin.tie(nullptr);
  66.  
  67.   long long n;
  68.   cin >> n;
  69.   vector<long long> a(n);
  70.   for(long long i=0;i<n;i++){
  71.     cin >> a[i];
  72.     a[i]=a[i]-i;
  73.   }
  74.  
  75.   vector<long long> res(n);
  76.   sol(0,n-1,-(1ll<<40),(1ll<<40),a,res);
  77.  
  78.   long long gap=0;
  79.  
  80.   for(long long i=0;i<n;i++){
  81.     // if(i){cout << " ";}
  82.     gap+=abs(res[i]-a[i]);
  83.     // cout << res[i]+i << "\n";
  84.     // cout << res[i]+i;
  85.   }//cout << "\n";
  86.   cout << gap << "\n";
  87.   for(long long i=0;i<n;i++){
  88.     if(i){cout << " ";}
  89.     cout << res[i]+i;
  90.   }cout << "\n";
  91.   return 0;
  92. }
Success #stdin #stdout 0.01s 5240KB
comments (?)
stdin
copy 
7
9 4 8 20 14 15 18
stdout
copy 
13
4 5 8 13 14 15 18
https://ideone.com/SYavXR
language:
C++14 (gcc 8.3)
created:
19 days ago
visibility:
secret

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!