Skip to content

Instantly share code, notes, and snippets.

@swapnil-warke
Created July 31, 2013 19:00
Show Gist options
  • Save swapnil-warke/6125047 to your computer and use it in GitHub Desktop.
Save swapnil-warke/6125047 to your computer and use it in GitHub Desktop.
counting inversions same as uva11495
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
typedef long long ll;
ll c_i;
template <class T>
void Merge(T a[],T temp[],ll low,ll high)
{
ll mid=(high+low)/2;
ll i=low;
ll j=mid+1;
ll k=low;
while(i<=mid && j<=high)
{
if(a[i]<=a[j])
temp[k++]=a[i++];
else
{
temp[k++]=a[j++];
c_i+=(mid-i+1);
}
}
while(i<=mid) temp[k++]=a[i++];
while(j<=high) temp[k++]=a[j++];
//copy back temp in
for(ll z=low;z<=high;z++) a[z]=temp[z];
}
template <class T>
void MergeSort(T a[],T temp[],ll low,ll high)
{
if(low<high)
{
ll mid=(low+high)/2;
MergeSort(a,temp,low,mid);
MergeSort(a,temp,mid+1,high);
Merge<T>(a,temp,low,high);
}
}
int main()
{
ll a[500001],t[500001];
while(1)
{
ll n;
cin>>n;
if(n==0) break;
for(int i=1;i<=n;i++)
cin>>a[i];
c_i=0;
MergeSort<ll>(a,t,1,n);
// for(int i=1;i<=n;i++)
// cout<<a[i]<<" ";
cout<<c_i<<endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment