oj.uz

Submission #273373

# Submission time Handle Problem Language Result Execution time Memory
273373 2020-08-19T05:04:10 Z 반딧불(#5107) Exercise Deadlines (CCO20_day1problem2) C++17
0 / 25
 6 ms 1280 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;
set<int> st;

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

int segTree[800002];
void initialize(int i, int l, int r){
    if(l==r) segTree[i] = arr[l];
    else{
        int m = (l+r)>>1;
        initialize(i*2, l, m), initialize(i*2+1, m+1, r);
        segTree[i] = max(segTree[i*2], segTree[i*2+1]);
    }
}
int setVal(int i, int l, int r, int idx, int val){
    if(l==r) segTree[i] = val;
    else{
        int m = (l+r)>>1;
        if(idx<=m) setVal(i*2, l, m, idx, val);
        else setVal(i*2+1, m+1, r, idx, val);
        segTree[i] = max(segTree[i*2], segTree[i*2+1]);
    }
}
int maxIdx(int i, int l, int r, int val){
    if(l==r) return l;
    int m = (l+r)>>1;
    if(segTree[i*2+1] >= val) return maxIdx(i*2+1, m+1, r, val);
    return maxIdx(i*2, l, m, val);
}

ll ans;

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

    initialize(1, 1, n);
    for(int i=1; i<=n; i++) add(i, 1);

    for(int i=n; i>=1; i--){
        int x = *st.rbegin();
        int tmp = maxIdx(1, 1, n, i);

        ans += sum(tmp)-1;
        st.erase(tmp);
        add(tmp, -1);
        setVal(1, 1, n, tmp, 0);
    }

    printf("%lld", ans);
}

Compilation message

Main.cpp: In function 'int setVal(int, int, int, int, int)':
Main.cpp:56:1: warning: no return statement in function returning non-void [-Wreturn-type]
   56 | }
      | ^
Main.cpp: In function 'int main()':
Main.cpp:75:13: warning: unused variable 'x' [-Wunused-variable]
   75 |         int x = *st.rbegin();
      |             ^
Main.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:68:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |     for(int i=1; i<=n; i++) scanf("%d", &arr[i]), st.insert(i);
      |                             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 1280 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 1280 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -