inversion count

general
,
1

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;
	}
}
2
1 Like
3

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;

    }