# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
307134 | Tamarpeikrishvili | Exercise Deadlines (CCO20_day1problem2) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int tree[200005]
long long ans = 0;
vector <int> v[200005];
priority_queue <int> pq;
int get(int idx){
int sum = 0;
while (idx > 0){
sum += tree[idx];
idx = idx - (idx & -idx);
}
return sum;
}
void upd(int idx ,int val, int MaxVal){
while (idx <= MaxVal){
tree[idx] += val;
idx += (idx & -idx);
}
}
int main (){
int n;
cin >> n;
int a[n];
for(int i=1; i<=n; i++) {
cin >> a[i];
v[a[i]].push_back(i);
}
sort(a+1, a+n+1);
for(int i=1; i<=n; i++){
if(a[i] < i){
cout << -1 << endl;
return 0;
}
}
for(int i=1; i<=n; i++) upd(i , 1, n);
for(int i=n; i>0; i--){
for(int j=0; j<v[i].size(); j++) {
pq.push(v[i][j]);
}
int k = pq.top();
pq.pop();
upd(n - k + 1, -1, n);
ans = get(n - k + 1) + ans;
}
cout << ans;
}