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;
    

    }

  • //