Submission #46402

#	Time	Username	Problem	Language	Result	Execution time	Memory
46402		ffresh	즐거운 채소 기르기 (JOI14_growing)	C++17	100 / 100	123 ms	20936 KiB

growing

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 3e5+15;

int pen[N];

void update(int ind,int add){
    while(ind<N)
        pen[ind]+=add,ind +=ind&(-ind);
}   

int query(int ind){
    int ret=0;
    while(ind)
        ret += pen[ind],ind = ind&(ind-1);
    return ret;
}   
pair<int,int> ar[N];

int min_cost(int ind,int n){
    return  min(ind-1 - query(ind-1), n-ind- (query(n)- query(ind)));
}
int main(){
    
    //freopen("input.txt","r",stdin);

    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
        scanf("%d",&ar[i].first);
        ar[i].second = i;
    }
    sort(ar+1,ar+n+1);
    long long ret=0;
    int i;
    for(i=1;i<=n;){
        int l = i,r= i;
        
        while(r<=n){
            if(ar[r].first==ar[l].first)++r;
            else
                break;
        }

        --r;
        
        i = r+1;

        while(l<=r){
            int acost = min_cost(ar[l].second,n);
            int bcost = min_cost(ar[r].second,n);
            if(acost<bcost){
                ret += acost;
                update(ar[l].second,1);
                ++l;
            }
            else{
                ret +=bcost;
                update(ar[r].second,1);
                --r;
            }
        }
    }
    cout<<ret<<endl;

    return 0;
}

Compilation message (stderr)

growing.cpp: In function 'int main()':
growing.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&ar[i].first);
         ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 15 / 15
• Subtask 4: 55 / 55