Submission #168154

#TimeUsernameProblemLanguageResultExecution timeMemory
168154rzbtKrov (COCI17_krov)C++14
0 / 140
365 ms9056 KiB
#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; //printf(" %lld %lld %lld %lld %lld %lld %lld %lld %lld %lld %lld\n",krov,h,vl,vd,prel,poslel,pred,posled,pl,pd,pokl->F); return (h-niz[krov]>0?h-niz[krov]:-h+niz[krov])+(zd-dobij(pd,bitd))-vd*(td-dobij(pd,imad))+vd*dobij(pd,imad)-dobij(pd,bitd) +(zl-dobij(pl,bitl))-vl*(tl-dobij(pl,imal))+vl*dobij(pl,imal)-dobij(pl,bitl); } ll ternarna(ll l,ll d,ll krov,ll sol){ if(d-l<=3){ 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)); } bool proveri(ll krov, ll h){ 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; return dobij(pl,imal)+dobij(pl,imad)>=(n-n/2); } ll nadjiopt(ll l,ll d,ll krov,ll sol){ if(l>d)return sol; ll h=(l+d)/2; if(proveri(krov,h))return nadjiopt(l,h-1,krov,h); return nadjiopt(h+1,d,krov,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; sort(all(tvL)); 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(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),MAXN+1e9,i,LLONG_MAX)); res=min(res,resi(nadjiopt(max(i,n-i+1),MAXN+MAXN+1e9,i,-1),i)); 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 'bool proveri(ll, ll)':
krov.cpp:84:8: warning: variable 'pd' set but not used [-Wunused-but-set-variable]
     ll pd;
        ^~
krov.cpp: In function 'int main()':
krov.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &n);
     ~~~~~^~~~~~~~~~~~
krov.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",niz+i);
         ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...