[algogeeks] Re: Finding total number of inversions in an array in O(nlogn) complexity .

[KK]

This code is not getting AC on spoj.. m not able to point out the
error plzzz help.....
Here is the link to this problem at spoj : http://www.spoj.pl/problems/INVCNT/


#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

void MergeSort(vector<int> &v, int p, int r);
void Merge(vector<int> &v, int p, int q, int r);
void PrintArray(vector<int> v);

int count;

int main()
{
    extern int count;
    int n, i, t;
    vector<int> v;

    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    cin >> t;
    while(t--)
    {
    getchar();
    count = 0;
    scanf("%d",&n);
    v.resize(n);

    for(i=0; i<n; i++)
         scanf("%d",&v[i]);

    //cout << "The Input array is:" << endl;
    //PrintArray(v);

    MergeSort(v,0,n-1);

    //cout << "The Sorted array is:" << endl;
    //PrintArray(v);
    cout << count << endl;
    }
    return 0;
}

void MergeSort(vector<int> &v, int p, int r)
{
     if(p < r)
     {
          int q = (p+r)/2;
          MergeSort(v,p,q);
          MergeSort(v,q+1,r);
          Merge(v,p,q,r);
     }
}

void Merge(vector<int> &v, int p, int q, int r)
{
     extern int count;
     int i, j, k;
     vector<int> v1, v2;
     v1.resize(q-p+1);
     v2.resize(r-q);

     k=0;
     for(i=p; i<=q; i++)
         v1[k++] = v[i];

     k=0;
     for(i=q+1; i<=r; i++)
         v2[k++] = v[i];

     v1.push_back(INT_MAX);
     v2.push_back(INT_MAX);

     i=0; j=0;
     for(k=p; k<=r ;k++)
     {
          if(v1[i] < v2[j])
          {
              v[k] = v1[i++];
              count += j;      // when taking element from 1st array
Incrementing count by no of elements already taken from 2nd array
          }
          else
              v[k] = v2[j++];
     }
}
void PrintArray(vector<int> &v)
{
     int i,n = v.size();
     for(i=0; i<n; i++)
         printf("%d ",v[i]);
     printf("\n");
}

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.