Submission #486363

#	Time	Username	Problem	Language	Result	Execution time	Memory
486363		urd05	즐거운 채소 기르기 (JOI14_growing)	C++17	100 / 100	74 ms	7312 KiB

growing

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

int tree[300001];

int sum(int i) {
    int ret=0;
    while (i>0) {
        ret+=tree[i];
        i-=(i&-i);
    }
    return ret;
}

void update(int i,int val) {
    while (i<=300000) {
        tree[i]+=val;
        i+=(i&-i);
    }
}

typedef pair<int,int> P;

int main() {
    int n;
    scanf("%d",&n);
    vector<P> v;
    for(int i=1;i<=n;i++) {
        int x;
        scanf("%d",&x);
        v.push_back(P(x,i));
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    long long ret=0;
    int ind=0;
    while (ind<v.size()) {
        int save=ind;
        while (ind<v.size()&&v[ind].first==v[save].first) {
            ret+=min(sum(v[ind].second-1),sum(n)-sum(v[ind].second));
            ind++;
        }
        for(int j=save;j<ind;j++) {
            update(v[j].second,1);
        }
    }
    printf("%lld",ret);
    return 0;
}

Compilation message (stderr)

growing.cpp: In function 'int main()':
growing.cpp:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     while (ind<v.size()) {
      |            ~~~^~~~~~~~~
growing.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         while (ind<v.size()&&v[ind].first==v[save].first) {
      |                ~~~^~~~~~~~~
growing.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
growing.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         scanf("%d",&x);
      |         ~~~~~^~~~~~~~~

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