#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);
| ~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
6 ms |
1280 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
6 ms |
1280 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |