Submission #25812

#	Time	Username	Problem	Language	Result	Execution time	Memory
25812		tlwpdus	즐거운 채소 기르기 (JOI14_growing)	C++98	100 / 100	159 ms	14776 KiB

growing

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 15 / 15
• Subtask 4: 55 / 55