Submission #123919

#	Time	Username	Problem	Language	Result	Execution time	Memory
123919		songc	즐거운 채소 기르기 (JOI14_growing)	C++14	100 / 100	152 ms	9316 KiB

growing

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N;
int A[303030], L[303030], R[303030], T[303030];
vector<int> comp;
LL ans;

void update(int t){
    while (t<=N){
        T[t]++;
        t += t & -t;
    }
}

int read(int t){
    int ret=0;
    while (t){
        ret += T[t];
        t -= t & -t;
    }
    return ret;
}

int main(){
    scanf("%d", &N);
    for (int i=1; i<=N; i++) {
        scanf("%d", &A[i]);
        comp.push_back(A[i]);
    }
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    for (int i=1; i<=N; i++) A[i] = lower_bound(comp.begin(), comp.end(), A[i]) - comp.begin() + 1;
    for (int i=1; i<=N; i++){
        L[i] = read(N)-read(A[i]);
        update(A[i]);
    }
    memset(T, 0, sizeof T);
    for (int i=N; i>=1; i--){
        R[i] = read(N)-read(A[i]);
        update(A[i]);
    }
    for (int i=1; i<=N; i++) ans += min(L[i], R[i]);
    printf("%lld\n", ans);
    return 0;
}

Compilation message (stderr)

growing.cpp: In function 'int main()':
growing.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
growing.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~

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