oj.uz

Submission #25812

# Submission time Handle Problem Language Result Execution time Memory
25812 2017-06-24T08:05:34 Z tlwpdus 즐거운 채소 기르기 (JOI14_growing) C++
100 / 100
 159 ms 14776 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int arr[300100];
int ord[300100];
int tree[1050000];
int key = 524288;

void upd(int idx, int val) {
    idx+=key;
    while(idx>0) {
        tree[idx] += val;
        idx>>=1;
    }
}

int getv(int s, int e) {
    int sum = 0;
    s+=key;e+=key;
    while(s<=e) {
        if (s&1) sum += tree[s++];
        if (~e&1) sum += tree[e--];
        s>>=1;e>>=1;
    }
    return sum;
}

bool cmp(int a, int b) {
    return arr[a]!=arr[b]?arr[a]<arr[b]:a>b;
}

ll res;
int sz = 1;
vector<int> loc;
ll l[300100];
ll r[300100];
void solve() {
    int i;
    for (i=0;i<loc.size();i++) l[i] = ((i)?l[i-1]:0LL)+1LL*(loc[i]-i);
    for (i=(int)loc.size()-1;i>=0;i--) r[i] = ((i+1==loc.size())?0LL:r[i+1])+1LL*(sz-(loc.size()-i)-loc[i]);
    ll mini = min(r[0],l[(int)loc.size()-1]);
    for (i=0;i+1<loc.size();i++) if (mini>l[i]+r[i+1]) mini=l[i]+r[i+1];
    res += mini;
    loc.clear();
}

int main() {
    int i;

    scanf("%d",&n);
    for (i=0;i<n;i++) scanf("%d",&arr[i]);
    for (i=0;i<n;i++) ord[i] = i;
    sort(ord,ord+n,cmp);
    for (i=n-1;i>=0;i--,sz++) {
        loc.push_back(getv(0,ord[i]));
        upd(ord[i],1);
        if (i==0||arr[ord[i]]!=arr[ord[i-1]]) solve();
    }
    printf("%lld\n",res);

    return 0;
}

Compilation message

growing.cpp: In function 'void solve()':
growing.cpp:43:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<loc.size();i++) l[i] = ((i)?l[i-1]:0LL)+1LL*(loc[i]-i);
               ^
growing.cpp:44:52: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=(int)loc.size()-1;i>=0;i--) r[i] = ((i+1==loc.size())?0LL:r[i+1])+1LL*(sz-(loc.size()-i)-loc[i]);
                                                    ^
growing.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i+1<loc.size();i++) if (mini>l[i]+r[i+1]) mini=l[i]+r[i+1];
                 ^
growing.cpp: In function 'int main()':
growing.cpp:54:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
growing.cpp:55:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i=0;i<n;i++) scanf("%d",&arr[i]);
                                          ^

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
15.0 / 15.0

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

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 13156 KB Output is correct
2 Correct 46 ms 13156 KB Output is correct
3 Correct 79 ms 13428 KB Output is correct
4 Correct 126 ms 13428 KB Output is correct
5 Correct 66 ms 13156 KB Output is correct
6 Correct 56 ms 13156 KB Output is correct
7 Correct 143 ms 14008 KB Output is correct
8 Correct 156 ms 13156 KB Output is correct
9 Correct 156 ms 14776 KB Output is correct
10 Correct 159 ms 13156 KB Output is correct