fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long int ans=0;
  5. int arr[200001];
  6.  
  7. void merge(int *arr,int left,int middle,int right)
  8. {
  9. 	int i,j,k;
  10. 	int n1=middle-left+1;
  11. 	int n2=right-middle;
  12. 	int a[n1]={0};
  13. 	int b[n2]={0};
  14. 	for(int i=0;i<n1;++i)
  15. 	{
  16. 		a[i]=arr[left+i];
  17. 	}
  18. 	for(int j=0;j<n2;++j)
  19. 	{
  20. 		b[j]=arr[j+middle+1];
  21. 	}
  22. 	i=0;j=0;k=left;
  23. 	while(i<n1 and j<n2)
  24. 	{
  25. 		if(a[i]<=b[j])
  26. 		{
  27. 			arr[k]=a[i];
  28. 			++i;
  29. 			++k;
  30. 		}
  31. 		if(b[j]<a[i])
  32. 		{	
  33. 			ans+=(n1-i);
  34. 			arr[k]=b[j];
  35. 			++j;
  36. 			++k;
  37. 		}
  38. 	}
  39. 	while(i<n1)
  40. 	{
  41. 		arr[k]=a[i];
  42. 		++k;
  43. 		++i;
  44. 	}
  45. 	while(j<n2)
  46. 	{
  47. 		arr[k]=b[j];
  48. 		++j;
  49. 		++k;
  50. 	}
  51. }
  52.  
  53. void merge_sort(int *arr,int first,int last)
  54. {
  55. 	if(first<last)
  56. 	{
  57. 		int mid=(first+last)/2;
  58. 		merge_sort(arr,0,mid);
  59. 		merge_sort(arr,mid+1,last);
  60. 		merge(arr,first,mid,last);
  61. 	}
  62. }
  63.  
  64. int main()
  65. {
  66. 	ios_base::sync_with_stdio(false);	
  67. 	cin.tie(NULL);
  68. 	int p{0};
  69. 	cin>>p;
  70. 	while(p)
  71. 	{
  72. 	int n{0};
  73. 	cin>>n;
  74. 	ans=0;
  75. 	for(int i=0;i<n;++i)
  76. 	{
  77. 		cin>>arr[i];
  78. 	}
  79. 	merge_sort(arr,0,n-1);
  80. 	cout<<ans<<"\n";
  81. 	--p;
  82. 	}
  83. 	return 0;
  84. }
Success #stdin #stdout 0s 4500KB
comments (?)
stdin
copy 
2

3
3
1
2

5
2
3
8
6
1
stdout
copy 
2
5
https://ideone.com/xa6Xv1
language:
C++14 (gcc 8.3)
created:
4 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!