# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
305556 | nickmet2004 | Exercise Deadlines (CCO20_day1problem2) | C++11 | 124 ms | 11892 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;
const int N = 2e5 + 5;
int n , d[N];
int F[N];
vector<int> E[N];
void upd(int i , int v){
for(; i <=n; i += i & -i) F[i]+=v;
}
int get(int i){
int sum = 0;
for(; i; i -= i & -i) sum += F[i]; return sum;
}
int main (){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
for(int i = 1; i <= n; ++i) cin >> d[i] ,E[d[i]].emplace_back(i);
sort(d+ 1 , d + n + 1); for(int i=1; i<= n; ++i) if(d[i] < i){cout << -1; return 0;}
for(int i = 1; i <= n; ++i) upd(i , 1);
priority_queue<int> pq;
int ans =0;
for(int i = n; i; --i){
for(int x : E[i]) pq.push(x);
int a= pq.top(); pq.pop();
upd(n - a + 1 ,-1);
ans += get(n - a + 1);
}cout << ans;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |