oj.uz

Submission #273253

# Submission time Handle Problem Language Result Execution time Memory
273253 2020-08-19T04:37:10 Z 반딧불(#5107) Exercise Deadlines (CCO20_day1problem2) C++17
0 / 25
 4 ms 640 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int arr[200002];

void checkIfAble(){
    vector<int> v(arr+1, arr+n+1);
    sort(v.begin(), v.end());
    for(int i=1; i<=n; i++){
        if(v[i-1] < i){
            printf("-1");
            exit(0);
        }
    }
}
vector<pair<int, int> > v;

int tree[200002];
void add(int x, int val){
    while(x<=n){
        tree[x] += val;
        x += x&(-x);
    }
}
int sum(int x){
    int ret = 0;
    while(x){
        ret += tree[x];
        x -= x&(-x);
    }
    return ret;
}

ll ans;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
    checkIfAble();

    for(int i=1; i<=n; i++){
        v.push_back({arr[i], -i});
    }
    sort(v.begin(), v.end());
    set<int> st;
    for(int i=1; i<=n; i++) st.insert(i);
    for(int i=0; i<n; i++){
        auto it = st.upper_bound(v[i].first);
        --it;
        if(*it > -v[i].second){
            it = st.lower_bound(-v[i].second);
            if(it != st.begin() && *it != -v[i].second){
                auto it2 = prev(it);
                if(*it - (-v[i].second) >= (-v[i].second) - *it2) swap(it, it2);
            }
        }


        arr[*it] = -v[i].second;
        st.erase(it);
    }

    for(int i=1; i<=n; i++){
        ans += (i-1-sum(arr[i]));
        add(arr[i], 1);
    }
    printf("%lld", ans);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:42:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |     for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 640 KB Output isn't correct
2 Halted 0 ms 0 KB -