oj.uz

Submission #42360

# Submission time Handle Problem Language Result Execution time Memory
42360 2018-02-26T13:37:51 Z nickyrio 즐거운 채소 기르기 (JOI14_growing) C++14
100 / 100
 179 ms 5472 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 2 ms 480 KB Output is correct
4 Correct 1 ms 528 KB Output is correct
5 Correct 2 ms 536 KB Output is correct
6 Correct 2 ms 536 KB Output is correct
7 Correct 2 ms 712 KB Output is correct
8 Correct 2 ms 712 KB Output is correct
9 Correct 2 ms 712 KB Output is correct
10 Correct 2 ms 712 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
15.0 / 15.0

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

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1644 KB Output is correct
2 Correct 64 ms 2280 KB Output is correct
3 Correct 108 ms 3036 KB Output is correct
4 Correct 146 ms 3940 KB Output is correct
5 Correct 70 ms 3940 KB Output is correct
6 Correct 43 ms 3940 KB Output is correct
7 Correct 74 ms 5472 KB Output is correct
8 Correct 143 ms 5472 KB Output is correct
9 Correct 162 ms 5472 KB Output is correct
10 Correct 179 ms 5472 KB Output is correct