Submission #293916

#TimeUsernameProblemLanguageResultExecution timeMemory
293916sabamakuExercise Deadlines (CCO20_day1problem2)C++14
17 / 25
244 ms11616 KiB
#include<bits/stdc++.h> using namespace std; int n,d[200005],p[2000005]; vector <int> mp[200005]; priority_queue <int> q; int solve(int a){ int x = 0; for(int i = a; i > 0; i -= (i & -i)){ x += p[i]; } return x; } void update(int a){ for(int i = a + 1; i <= n; i += (i & -i)){ p[i]++; } } int a; int main(){ cin >> n; for(int i = 1; i <= n; i++){ cin >> d[i]; mp[d[i]].push_back(i); } sort(d + 1,d + n + 1); for(int i = 1; i <= n; i++){ if(d[i] < i){ cout << -1; return 0; } } int ans = 0; for(int i = n; i >= 1; i--){ for(int j = 0; j < mp[i].size(); j++){ q.push(mp[i][j]); } a = q.top(); q.pop(); int x = solve(a); ans += i - (a - x); update(a); } cout << ans; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:41:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(int j = 0; j < mp[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...