fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. int n;
  7. vector<int> d;
  8.  
  9. vector<int> bit;
  10.  
  11. void upd(int i, int v) {
  12. 	for (; i < n; i += (i+1) & (-i-1)) {
  13. 		bit[i] += v;
  14. 	}
  15. }
  16.  
  17. int query(int i) {
  18. 	int res = 0;
  19. 	for (; i >= 0; i -= (i+1) & (-i-1)) {
  20. 		res += bit[i];
  21. 	}
  22. 	return res;
  23. }
  24.  
  25. int main() {
  26. 	ios::sync_with_stdio(0), cin.tie(0);
  27. 	cin >> n;
  28. 	d.resize(n);
  29. 	for (int i = 0; i < n; i++) {
  30. 		cin >> d[i];
  31. 		d[i]--;
  32. 	}
  33. 	vector<int> p(n);
  34. 	set<int> zz;
  35. 	for (int i = 0; i < n; i++) zz.insert(i);
  36. 	for (int i = n-1; i >= 0; i--) {
  37. 		set<int>::iterator it = zz.upper_bound(d[i]);
  38. 		if (it == zz.begin()) {
  39. 			cout << -1 << '\n';
  40. 			exit(0);
  41. 		}
  42. 		--it;
  43. 		p[i] = *it;
  44. 		zz.erase(it);
  45. 	}
  46. 	bit.resize(n);
  47. 	ll tot = 0;
  48. 	for (int i = 0; i < n; i++) {
  49. 		tot += i - query(p[i]);
  50. 		upd(p[i], 1);
  51. 	}
  52. 	cout << tot << '\n';
  53. }
  54.  
Success #stdin #stdout 0s 4384KB
comments (?)
stdin
copy 
4
4 4 3 2
stdout
copy 
3
https://ideone.com/wE1HyM
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!