Submission #42359

#	Time	Username	Problem	Language	Result	Execution time	Memory
42359		nickyrio	즐거운 채소 기르기 (JOI14_growing)	C++14	0 / 100	6 ms	816 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() {
    #ifndef ONLINE_JUDGE
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    #endif // ONLINE_JUDGE
    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;
}

Compilation message (stderr)

growing.cpp: In function 'int main()':
growing.cpp:29:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("test.inp","r",stdin);
                                  ^
growing.cpp:30:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("test.out","w",stdout);
                                   ^

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