AC:
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
void MergeSort(vector<long>& v, long p, long r);
void Merge(vector<long> &v, long p, long q, long r);
void PrintArray(vector<long> v);
long long int count;
int main()
{
extern long long int count;
long n, i, t;
vector<long> v;
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
cin >> t;
while(t--)
{
count = 0;
scanf("%ld",&n);
v.resize(n);
for(i=0; i<n; i++)
scanf("%ld",&v[i]);
//cout << "The Input array is:" << endl;
//PrintArray(v);
MergeSort(v,0,n-1);
//cout << "The Sorted array is:" << endl;
//PrintArray(v);
printf("%lld\n\n",count);//count << endl;
}
return 0;
}
void MergeSort(vector<long>& v, long p, long r)
{
if(p < r)
{
long q = (p+r)/2;
MergeSort(v,p,q);
MergeSort(v,q+1,r);
Merge(v,p,q,r);
}
}
void Merge(vector<long>& v, long p, long q, long r)
{
extern long long count;
long 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)
{
long i,n = v.size();
for(i=0; i<n; i++)
printf("%ld ",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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
