fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. long long c=0;
  5. long long merge(int ar[],int low,int mid,int high)
  6. {
  7. 	int p=low,q=mid+1,k=0;
  8. 	long long count=0;
  9. 	int temp[high-low+1];
  10. 	while(p<=mid && q<=high)
  11. 	{
  12. 		if(ar[p]<=ar[q])
  13. 		{
  14. 			temp[k++] = ar[p++];
  15. 		}
  16. 		else
  17. 		{
  18. 			count += mid-p+1;
  19. 			temp[k++] = ar[q++];
  20. 		}
  21. 	}
  22. 	while(p<=mid)
  23. 	{
  24. 		temp[k++] = ar[p++];
  25. 	}
  26. 	while(q<=high)
  27. 	temp[k++] = ar[q++];
  28. 	for(int i=low;i<=high;i++)
  29. 	{
  30. 		ar[i] = temp[i-low];
  31. 	}
  32. 	return count;
  33. }
  34. void breakArr(int ar[],int n,int low,int high)
  35. {
  36. 	if(high==low)
  37. 	return;
  38. 	int mid = (low+high)/2;
  39. 	breakArr(ar,n,low,mid);
  40. 	breakArr(ar,n,mid+1,high);
  41. 	c = c + merge(ar,low,mid,high);
  42. }
  43. int main() {
  44. 	int t,n;
  45. 	cin>>t;
  46. 	while(t--)
  47. 	{
  48. 		c=0;
  49. 		cin>>n;
  50. 		int a[n];
  51. 		for(int i=0;i<n;i++)
  52. 		cin>>a[i];
  53. 		breakArr(a,n,0,n-1);
  54. 		cout<<c<<endl;
  55. 	}
  56. 	return 0;
  57. }
Success #stdin #stdout 0s 5680KB
comments (?)
stdin
copy 
2

3
3
1
2

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