Submission #42360

#	Time	Username	Problem	Language	Result	Execution time	Memory
42360		nickyrio	즐거운 채소 기르기 (JOI14_growing)	C++14	100 / 100	179 ms	5472 KiB

growing

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define DEBUG(x) { cerr << #x << " = " << x << endl; }
#define Arr(A, l, r) { cerr << #A  << " = "; FOR(_, l, r) cerr << A[_] << ' '; cerr << endl; }
#define N 1001000
#define pp pair<int, int>
#define next __next
#define prev __prev
#define __builtin_popcount __builtin_popcountll
#define bit(S, i) (((S) >> i) & 1)
#define IO ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);

using namespace std;

int n, a[N], BIT[N], f[N];
vector<int> ranking;

void Up(int u) { for (; u > 0; u -= u & -u) BIT[u]++; }
int Get(int u) {
    int ans = 0;
    for (; u <= n; u += u & -u) ans += BIT[u];
    return ans;
}

int main() {
    IO;
    cin >> n;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, n) ranking.push_back(a[i]);
    sort(ranking.begin(), ranking.end());
    FOR(i, 1, n) {
        int idx = lower_bound(ranking.begin(), ranking.end(), a[i]) - ranking.begin() + 1;
        f[i] = Get(idx + 1);
        Up(idx);
    }
    FOR(i, 1, n) BIT[i] = 0;
    long long ans = 0;
    FORD(i, n, 1) {
        int idx = lower_bound(ranking.begin(), ranking.end(), a[i]) - ranking.begin() + 1;
        ans += min(f[i], Get(idx + 1));
        Up(idx);
    }
    cout << ans;
}

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