oj.uz

Submission #486363

# Submission time Handle Problem Language Result Execution time Memory
486363 2021-11-11T12:28:58 Z urd05 즐거운 채소 기르기 (JOI14_growing) C++17
100 / 100
 74 ms 7312 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 2 ms 484 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 3 ms 508 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 1092 KB Output is correct
2 Correct 24 ms 2496 KB Output is correct
3 Correct 39 ms 3648 KB Output is correct
4 Correct 49 ms 4660 KB Output is correct
5 Correct 33 ms 4684 KB Output is correct
6 Correct 22 ms 2496 KB Output is correct
7 Correct 62 ms 5124 KB Output is correct
8 Correct 72 ms 7196 KB Output is correct
9 Correct 71 ms 7216 KB Output is correct
10 Correct 74 ms 7312 KB Output is correct