fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3.  
  4. typedef long long ll;
  5.  
  6.  
  7. using namespace std;
  8.  
  9.  
  10. constexpr int MAXN = 2e5 + 1;
  11.  
  12. vector<int> tree(2 * MAXN , 0);
  13.  
  14. void modify(int p , int val)
  15. {
  16. 	for(tree[p += MAXN] += val ; p > 1 ; p /= 2)
  17. 	{
  18. 		tree[p / 2] = tree[p] + tree[p ^ 1];
  19. 	}
  20. }
  21.  
  22. int sum(int l , int r) //[l , r)
  23. {
  24. 	int res = 0;
  25. 	for(l += MAXN , r += MAXN ; l < r ; l /= 2 , r /= 2)
  26. 	{
  27. 		if(l % 2)
  28. 		{
  29. 			res += tree[l];
  30. 			++l;
  31. 		}
  32.  
  33. 		if(r % 2)
  34. 		{
  35. 			--r;
  36. 			res += tree[r];
  37. 		}
  38. 	}
  39.  
  40. 	return res;
  41. }
  42.  
  43. int main() {
  44. 	int n;
  45. 	cin >> n;
  46.  
  47. 	vector<int> p(n);
  48. 	for(auto& el : p) cin >> el;
  49.  
  50. 	ll ans = 0;
  51.  
  52. 	for(int i = n - 1 ; i >= 0 ; --i)
  53. 	{
  54. 		ans += sum(0 , p[i]);
  55. 		modify(p[i] , 1);
  56. 	}
  57.  
  58. 	cout << ans << endl;
  59.  
  60. 	return 0;
  61. }
Success #stdin #stdout 0s 4676KB
comments (?)
stdin
copy 
5
1 20 6 4 5
stdout
copy 
5
https://ideone.com/tu4uLg
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!