fork(1) download
copy 
  1. #include<iostream>
  2. using namespace std;
  3. long long int c=0;
  4. void count( long long int a[],	long long int lb,long long int mid,long long int ub)
  5. {
  6. 	long long int left = mid-lb+1;
  7. 	long long int right = ub - mid;
  8. 	long long int l[left];
  9. 	long long int r[right];
  10. 	for(long long int i=0;i<left;i++)
  11. 	{
  12. 		l[i]=a[i+lb];
  13. 	}
  14. 	for(long long int i=0;i<left;i++)
  15. 	{
  16. 		r[i]=a[mid+i+1];
  17. 	}
  18. 	long long int i=0,j=0,k=lb;
  19. 	while(i<left && j<right)
  20. 	{
  21. 		if(l[i]>r[j])
  22. 		{
  23. 			a[k] = r[j];
  24. 			k++;
  25. 			c = c+ (left-i);
  26. 			j++;
  27. 		}
  28. 		else
  29. 		{
  30. 			a[k] = l[i];
  31. 			k++;
  32. 			c=c;
  33. 			i++;
  34. 		}
  35. 	}
  36. 	while(i<left)
  37. 	{
  38. 		a[k]=l[i];
  39. 		i++,k++;
  40. 	}
  41. 	while(j<right)
  42. 	{
  43. 		a[k]=r[j];
  44. 		j++,k++;
  45. 	}
  46. }
  47. void inversion( long long int a[],long long int lb,long long int ub)
  48. {
  49.     long long int mid = (lb+ub)/2;
  50.      if(lb<ub)
  51.      {
  52.      	inversion(a,lb,mid);
  53.      	inversion(a,mid+1,ub);
  54.      	count(a,lb,mid,ub);
  55.      }
  56. } 
  57. int main()
  58. {
  59. 	int t;
  60. 	cin>>t;
  61. 	while(t--)
  62. 	{
  63.      long long int n;
  64.       cin>>n;
  65.       long long int a[200010];
  66.       for(long long int i=0;i<n;i++)
  67.       {
  68.       	cin>>a[i];
  69.       }
  70.       inversion(a,0,n-1);
  71.       cout<<c<<endl;
  72.       c=0;
  73. 	}
  74. 	return 0;
  75. }
Success #stdin #stdout 0s 4700KB
comments (?)
stdin
copy 
1
8
1 5 7 8 9 4 6 2
stdout
copy 
13
https://ideone.com/ooGjk8
problem INVCNT, based on SPOJ submission 27300604 (CPP14), 2021-01-19 09:02:32
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!