fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. long long join_vectors(vector<long long>& v, int p, int q, int r) {
  6. 	long long inv_cnt = 0;
  7. 	vector<long long> i_left(q-p+1), i_right(r-q);
  8. 	for (int i = 0; i < (q-p+1); ++i) i_left[i] = v[p+i];
  9. 	for (int i = 0; i < (r-q); ++i) i_right[i] = v[q+i+1];
  10. 	int i = 0, j = 0;
  11. 	for (int k = p; k <= r; ++k) {
  12. 		if (i_left[i] < i_right[j]) {v[k] = i_left[i]; ++i;}
  13. 		else {
  14. 			v[k] = i_right[j]; ++j;
  15. 			inv_cnt += (q-p+1) - i;
  16. 		}
  17. 	}
  18. 	return inv_cnt;
  19. }
  20.  
  21. long long count_inv(vector<long long>& v, int p, int r) {
  22. 	long long inv_cnt = 0;
  23. 	if (p < r) {
  24. 		int q = (p+r)/2;
  25. 		inv_cnt += count_inv(v, p, q);
  26. 		inv_cnt += count_inv(v, q+1, r);
  27. 		inv_cnt += join_vectors(v, p, q, r);
  28. 	}
  29. 	return inv_cnt;
  30. }
  31.  
  32. int main() {
  33. 	ios_base::sync_with_stdio(0); cin.tie(0);
  34. 	int t; cin >> t;
  35. 	while (t--) {
  36. 		int n; cin >> n;
  37. 		vector<long long> v(n);
  38. 		for (int i = 0; i < n; ++i) cin >> v[i];
  39. 		long long ic = count_inv(v, 0, v.size()-1);
  40. 		cout << ic << '\n';
  41. 	}
  42. 	return 0;
  43. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
2

3
3
1
2

5
2
3
8
6
1
stdout
copy 
2
5
https://ideone.com/UQHB6q
problem INVCNT, based on SPOJ submission 18135603 (C++14), 2016-11-08 18:49:55
language:
C++14 (gcc 8.3)
created:
7 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!