karlangadas

Inversion count spoj

Dec 8th, 2016
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. long long arr[200001];
  4. long long ans;
  5.  
  6. void merge(long long izq,long long mid,long long der){
  7.    
  8.     long long pos=0,posini=izq,ini2=mid+1;
  9.     long long arrtemp[der-izq+1];
  10.     while(izq<=mid&&ini2<=der){
  11.         if(arr[izq]<=arr[ini2])
  12.             arrtemp[pos++]=arr[izq++];
  13.         else{
  14.             ans=ans+(mid-izq+1);
  15.             arrtemp[pos++]=arr[ini2++];
  16.         }
  17.     }
  18.     while(izq<=mid) arrtemp[pos++]=arr[izq++];
  19.     while(ini2<=der) arrtemp[pos++]=arr[ini2++];
  20.     for(long long i=0;i<pos;i++)
  21.         arr[posini+i]=arrtemp[i];
  22.     return;
  23. }
  24.  
  25. void mergeSort(long long izq,long long der){
  26.     long long mid=(izq+der)/2;
  27.     if(izq<der){
  28.        
  29.         mergeSort(izq,mid);
  30.         mergeSort(mid+1,der);
  31.         merge(izq,mid,der);
  32.     }
  33. }
  34.  
  35. int main(){
  36.     long long ncases,nelem;
  37.     cin>>ncases;
  38.     while(ncases--){
  39.         ans=0;
  40.         cin>>nelem;
  41.         for(int i=0;i<nelem;i++)
  42.             cin>>arr[i];
  43.        
  44.         mergeSort(0,nelem-1);
  45.        
  46.         cout<<ans<<endl;
  47.     }
  48.     return 0;
  49. }
Advertisement
Add Comment
Please, Sign In to add comment