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

3
3
1
2

5
2
3
8
6
1
stdout
copy 
0
6
https://ideone.com/qbqms6
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!