# inversion count

I am trying to solve this(http://www.spoj.com/problems/INVCNT/) question…
I ma able to sort the array correctly using merge sort but am not able to get the correct inversion count…any help?
my solution

``````#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<stdlib.h>
#include<algorithm>
#define getcx getchar_unlocked
#ifndef ONLINE_JUDGE
#define getcx getchar
#endif
#define l long long
#define rep(i,n) for(l i=0;i<n;++i)
#define pi(n) printf("%d\n",n)
#define pl(n) printf("%lld\n",n)
#define MAX 100000
using namespace std;
inline void string(char *str)
{
register char c = 0;
register int i = 0;
while (c < 33)
c = getcx();
while (c != '\n') {
str[i] = c;
c = getcx();
i = i + 1;
}
str[i] = '\0';
}
inline int inp()
{
int n=0;
int ch=getcx();int sign=1;
while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();}

while(  ch >= '0' && ch <= '9' )
n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
return n*sign;
}
inline long long in()
{
long long n=0;
long long ch=getcx();long long sign=1;
while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();}

while(  ch >= '0' && ch <= '9' )
n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
return n*sign;
}
l merge(l a[200001],l p,l q,l r)
{
l n=q-p+1,m=r-q,count=0;
l b[n+1],c[m+1];
for(l i=0;i<n;++i)	//loop to store left sub array in temporary array
b[i]=a[p+i];
for(l i=0;i<m;++i)//loop to store right sub array in temporary array
c[i]=a[q+1+i];
l k=p,i=0,j=0;
for(;i<n&&j<m;++k)	//storing the values in original array
{
if(b[i]<=c[j])
{
a[k]=b[i];
++i;
}
else
{
a[k]=c[j];
++j;
count+=q-i;//if element in left sub array is greater than element in right sub array then number of inversions = q(mid)-i
}
}
while(i<n)
{
a[k]=b[i];
++i;++k;
}
while(j<m)
{
a[k]=c[j];
++k;++j;
}
return count;
}
l mergesort(l a[200001],l p,l r)
{
l count=0;
if(p<r)
{
l q=p+(r-p)/2;
count=mergesort(a,p,q);
count+=mergesort(a,q+1,r);
count+=merge(a,p,q,r);
}
return count;
}
main()
{
l t,n,a[200001],count;
t=in();
while(t--)
{
n=in();
for(l i=0;i<n;++i)
a[i]=in();
count=mergesort(a,0,n-1);
//	for(l i=0;i<n;++i)
//	cout<<a[i]<<" ";
cout<<count;
cout<<endl;
}
}``````
1 Like

I implemented more efficiently
HERE IS MY CODE:

#include<bits/stdc++.h>

using namespace std;

#define li long long int

vector

• arr(200001);

li n;
li mrgsrt(li l, li r)

{

``````li co=0;
if(l>=r)
return 0;
li temp[r-l+5];
li mid=(l+r)/2;
co+=mrgsrt(l, mid);
co+=mrgsrt(mid+1, r);
li i=l, j=mid+1, k=0;
for(; i<=mid&&j<=r; )
{

if(arr[i]<=arr[j])
temp[k++]=arr[i++];
else
{

temp[k++]=arr[j++];
co+=(mid-i+1);

}

}
while(i<=mid)
temp[k++]=arr[i++];
while(j<=r)
temp[k++]=arr[j++];
j=l;
for(i=0; i<k; ++i)
arr[j++]=temp[i];
return co;
``````

}

int main()

{

``````li te;

cin>>te;

while(te--)
{

cin>>n;

for(li i=0; i<n; ++i)
cin>>arr[i];

li ans=mrgsrt(0, n-1);

cout<<ans<<endl;

}

return 0;
``````

}

• //