fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. long long inversionCount(long long a[], long long f, long long mid, long long l){
  5. 	long long x[200005], y[200005], c=0;
  6. 	long long i,j,xl,yl,k;
  7. 	//cout << "Sorted array 1 with f and l " << f << " " << mid << " - ";
  8. 	for(i=0;i<(mid-f)+1;i++){
  9. 		x[i] = a[f+i];
  10. 		//cout << x[i] << " ";
  11. 	}
  12. 	//cout << "\n";
  13. 	xl = i;
  14.  
  15. 	//cout << "Sorted array 2 with f and l " << mid+1 << " " << l << " - ";
  16. 	for(i=0;i<l-mid;i++){
  17. 		y[i] = a[mid+1+i];
  18. 		//cout << y[i] << " ";
  19. 	}
  20. 	//cout << "\n";
  21. 	yl = i;
  22.  
  23. 	i=0; j=0, k=f;
  24. 	while(i<xl && j<yl){
  25. 		if(x[i] > y[j]){
  26. 			//cout << x[i] << " " << y[j] << "\n";
  27. 			c = c + (xl-i);
  28. 			a[k] = y[j];
  29. 			j++;
  30. 		} else {
  31. 			a[k] = x[i];
  32. 			i++;
  33. 		}
  34. 		k++;
  35. 	}
  36.  
  37. 	if(i<xl){
  38. 		a[k] = x[i];
  39. 		//cout << x[i] << "AA\n";
  40. 		k++; i++;
  41. 	}
  42.  
  43. 	if(j<yl){
  44. 		a[k] = y[j];
  45. 		k++; j++;
  46. 	}
  47.  
  48. 	return c;
  49. }
  50.  
  51. long long findInversions(long long a[], long long f, long long l){
  52. 	long long x,y,z;
  53. 	if(f>=l){
  54. 		return 0;
  55. 	}
  56.  
  57. 	long long mid = (f+l)/2;
  58. 	//cout << "11111 " << f << " " << mid << "\n";  
  59. 	//cout << "22222 " << mid+1 << " " << l << "\n";
  60. 	x = findInversions(a,f,mid);
  61. 	y = findInversions(a,mid+1,l);
  62. 	//cout << "3333" << f << " " << mid << " " << l << "\n";
  63. 	z = inversionCount(a,f,mid,l);
  64.  
  65. 	return x+y+z;
  66. }
  67.  
  68. int main() {
  69. 	long long t,i,a[200005];
  70.  
  71. 	cin >> t;
  72.  
  73. 	while(t--){
  74. 		long long n;
  75. 		cin >> n;
  76.  
  77. 		for(i=0;i<n;i++){
  78. 			cin >> a[i];
  79. 		}
  80.  
  81. 		long long c = findInversions(a,0,n-1);
  82. 		cout << c << "\n";
  83. 	}
  84. 	return 0;
  85. }
Success #stdin #stdout 0s 4484KB
comments (?)
stdin
copy 
3

3
3
1
2

5
2
3
8
6
1

3
1
1
1
stdout
copy 
2
5
0
https://ideone.com/FoDrDD
language:
C++ (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!