oj.uz

Submission #46402

# Submission time Handle Problem Language Result Execution time Memory
46402 2018-04-20T05:34:44 Z ffresh 즐거운 채소 기르기 (JOI14_growing) C++17
100 / 100
 123 ms 20936 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 2 ms 480 KB Output is correct
6 Correct 2 ms 540 KB Output is correct
7 Correct 2 ms 564 KB Output is correct
8 Correct 2 ms 564 KB Output is correct
9 Correct 2 ms 564 KB Output is correct
10 Correct 2 ms 624 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 624 KB Output is correct
2 Correct 2 ms 624 KB Output is correct
3 Correct 2 ms 624 KB Output is correct
4 Correct 2 ms 636 KB Output is correct
5 Correct 2 ms 636 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 2 ms 676 KB Output is correct
8 Correct 2 ms 680 KB Output is correct
9 Correct 2 ms 684 KB Output is correct
10 Correct 2 ms 688 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 736 KB Output is correct
4 Correct 3 ms 896 KB Output is correct
5 Correct 3 ms 980 KB Output is correct
6 Correct 3 ms 980 KB Output is correct
7 Correct 4 ms 1060 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 5 ms 1108 KB Output is correct
10 Correct 3 ms 1184 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1748 KB Output is correct
2 Correct 40 ms 3284 KB Output is correct
3 Correct 56 ms 5032 KB Output is correct
4 Correct 85 ms 7484 KB Output is correct
5 Correct 61 ms 9444 KB Output is correct
6 Correct 44 ms 9444 KB Output is correct
7 Correct 112 ms 12232 KB Output is correct
8 Correct 113 ms 15124 KB Output is correct
9 Correct 123 ms 18028 KB Output is correct
10 Correct 121 ms 20936 KB Output is correct