読者です 読者をやめる 読者になる 読者になる

らての精進日記

修行をします

joi春合宿2014 day1-2:Growing Vegetables is Fun

解法

しばらくBITとかを用いた嘘解法で戦ってて、嘘を嘘じゃなくすると満点が取れないことに気付いて絶望するなどした。

よく考えたら短いやつから順に貪欲的に端に寄せていけばいいと分かったのでBITとか使いながらやったら通った。

コード

#include<bits/stdc++.h>
using namespace std;
#define int long long

struct BIT{
    int N;
    vector<int>dat;

    void init(int n){
        N=n;
        dat.resize(N+1,0);
    }

    void add(int k,int x){
        k++;
        while(k<=N){
            dat[k]+=x;
            k+=k&-k;
        }
    }

    int getSum(int k){
        k++;
        int ret=0;
        while(k){
            ret+=dat[k];
            k-=k&-k;
        }
        return ret;
    }
};


int N;
int D[300000];
vector<int>hs;
vector<int>v[300000];

int mincost(BIT &bit,vector<int>&vec){
    int ret=0;
    for(int i=0;i<vec.size();i++){
        int l=(vec[i]-bit.getSum(vec[i]))-i;
        int r=N-1-vec[i]-(bit.getSum(N)-bit.getSum(vec[i]))-(vec.size()-1-i);
        ret+=min(l,r);
    }

    for(int i=0;i<vec.size();i++)bit.add(vec[i],1);
    return ret;
}

signed main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    //input
    cin>>N;
    for(int i=0;i<N;i++)cin>>D[i];

    
    //compress
    for(int i=0;i<N;i++)hs.push_back(D[i]);
    sort(hs.begin(),hs.end());
    hs.erase(unique(hs.begin(),hs.end()),hs.end());
    for(int i=0;i<N;i++){
        D[i]=lower_bound(hs.begin(),hs.end(),D[i])-hs.begin();
    }
    
    //solve
    for(int i=0;i<N;i++){
        v[D[i]].push_back(i);
    }

    int ans=0;
    BIT bit;
    bit.init(N+100);

    for(int i=0;i<N;i++){
        if(v[i].size()==0)continue;
        ans+=mincost(bit,v[i]);
    }
    cout<<ans<<endl;
}