oj.uz

Submission #42359

# Submission time Handle Problem Language Result Execution time Memory
42359 2018-02-26T13:37:16 Z nickyrio 즐거운 채소 기르기 (JOI14_growing) C++14
0 / 100
 6 ms 816 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() {
    #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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -