oj.uz

Submission #168155

# Submission time Handle Problem Language Result Execution time Memory
168155 2019-12-11T16:21:27 Z rzbt Krov (COCI17_krov) C++14
140 / 140
 483 ms 9584 KB 
#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(pd,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

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);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 632 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 5 ms 636 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 632 KB Output is correct
2 Correct 7 ms 632 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 632 KB Output is correct
2 Correct 10 ms 768 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 760 KB Output is correct
2 Correct 10 ms 760 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1016 KB Output is correct
2 Correct 16 ms 1016 KB Output is correct
3 Correct 11 ms 760 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 2740 KB Output is correct
2 Correct 94 ms 2800 KB Output is correct
3 Correct 104 ms 2780 KB Output is correct
4 Correct 136 ms 3316 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 3944 KB Output is correct
2 Correct 203 ms 4460 KB Output is correct
3 Correct 126 ms 4068 KB Output is correct
4 Correct 137 ms 3992 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 6728 KB Output is correct
2 Correct 261 ms 7032 KB Output is correct
3 Correct 169 ms 3816 KB Output is correct
4 Correct 355 ms 7008 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 9184 KB Output is correct
2 Correct 380 ms 9156 KB Output is correct
3 Correct 347 ms 7544 KB Output is correct
4 Correct 483 ms 9584 KB Output is correct
5 Correct 90 ms 3052 KB Output is correct