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>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 100005
typedef long long ll;
using namespace std;
ll n;
ll niz[MAXN];
ll bitl[MAXN],bitd[MAXN],imal[MAXN],imad[MAXN];
ll slikal[MAXN],slikad[MAXN];
vector<pair<ll,ll> > tvL,tvD;
ll zbirL,zbirD;
void dodaj(ll p,ll x,ll *bit){
for(;p<MAXN;p+=(-p)&p)
bit[p]+=x;
}
ll dobij(ll p,ll *bit){
ll z=0;
for(;p>0;p-=(-p)&p)
z+=bit[p];
return z;
}
ll tl;
ll td;
ll zl;
ll zd;
ll resi(ll h,ll krov ){
ll vl=h-krov;
ll vd=h+krov;
auto pokl=upper_bound(all(tvL),mp(vl,(ll)1e9+7));
ll pl;
if(pokl==tvL.end())pl=n;
else pl=slikal[pokl->second]-1;
auto pokd=upper_bound(all(tvD),mp(vd,(ll)1e9+7));
ll pd;
if(pokd==tvD.end())pd=n;
else pd=slikad[pokd->second]-1;
ll prel=vl*dobij(pl,imal)-dobij(pl,bitl);
ll poslel=(zl-dobij(pl,bitl))-vl*(tl-dobij(pl,imal));
ll pred=vd*dobij(pd,imad)-dobij(pd,bitd);
ll posled=(zd-dobij(pd,bitd))-vd*(td-dobij(pd,imad));
//printf(" %lld %lld %lld %lld %lld %lld %lld %lld %lld %lld\n",krov,h,vl,vd,prel,poslel,pred,posled,pl,pd);
return prel+poslel+pred+posled+(h-niz[krov]>0?h-niz[krov]:-h+niz[krov]);
}
ll ternarna(ll l,ll d,ll krov,ll sol){
if(d-l<=6){
for(ll i=l;i<=d;i++){
sol=min(sol,resi(i,krov));
}
return sol;
}
ll mid1=(l+l+d)/3;
ll mid2=(l+d+d)/3;
ll v1=resi(mid1,krov);
ll v2=resi(mid2,krov);
if(v1<v2)return ternarna(l,mid2,krov,min(v1,sol));
else return ternarna(mid1,d,krov,min(v2,sol));
}
ll res=LLONG_MAX;
int main()///PROMENI U LL
{
scanf("%lld", &n);
for(ll i=1;i<=n;i++)
scanf("%lld",niz+i);
for(ll i=1;i<=n;i++){
tvL.pb(mp(niz[i]-i,i));
}
ll brojac=1;
for(auto x:tvL){
slikal[x.S]=brojac;
brojac++;
}
for(ll i=1;i<=n;i++){
zd+=niz[i]+i;
tvD.pb(mp(niz[i]+i,i));
}
sort(all(tvL));
sort(all(tvD));
brojac=1;
for(auto x:tvD){
slikad[x.S]=brojac;
brojac++;
}
for(auto x:tvD)
dodaj(slikad[x.S],x.F,bitd);
for(auto x:tvD)
dodaj(slikad[x.S],1,imad);
td=n;
for(ll i=1;i<=n;i++){
dodaj(slikad[i],-niz[i]-i,bitd);
dodaj(slikad[i],-1,imad);
td--;
zd-=niz[i]+i;
res=min(res,ternarna(max(i,n-i+1),2e9,i,LLONG_MAX));
dodaj(slikal[i],niz[i]-i,bitl);
dodaj(slikal[i],1,imal);
tl++;
zl+=niz[i]-i;
}
printf("%lld",res);
return 0;
}
Compilation message (stderr)
krov.cpp: In function 'int main()':
krov.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &n);
~~~~~^~~~~~~~~~~~
krov.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",niz+i);
~~~~~^~~~~~~~~~~~~~
# | 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... |