fork download
copy 
  1.  
  2.     #include <iostream>
  3.     #define LL long long
  4.     using namespace std;
  5.     //Here start=left and end=right
  6.     LL merge(LL a[], LL start, LL mid, int end, LL temp[])
  7.     {
  8.         LL i,j,k;
  9.         LL ans = 0;
  10.         j = mid+1;
  11.         /*Inversion Count logic: if an element found in left array(sorted) is greater 
  12.           than all the remaining left elements are counted for inversion*/
  13.         for(k=start;k<=mid;k++)
  14.         {
  15.             while(j <= end)
  16.             {
  17.                 if(a[k] > a[j])
  18.                     j++;
  19.                 else
  20.                     break;
  21.             }
  22.             ans += j-(mid+1);
  23.         }
  24.         i=k=start;
  25.         j = mid+1;
  26.         while(i<=mid && j<=end)
  27.         {
  28.             if(a[i] < a[j])
  29.                 temp[k++] = a[i++];
  30.             else
  31.                 temp[k++] = a[j++];
  32.         }
  33.         while(i <= mid) temp[k++] = a[i++];
  34.         while(j <= end) temp[k++] = a[j++];
  35.         for(int i=start; i<=end; i++)
  36.             a[i] = temp[i];
  37.  
  38.         return ans;
  39.     }
  40.     LL mergesort(LL a[], LL start, LL end, LL temp[])
  41.     {
  42.         LL lc,rc,mc;
  43.         if(start < end)
  44.         {
  45.  
  46.             LL mid = (start + end)/2;
  47.             lc = mergesort(a, start, mid, temp);
  48.             rc = mergesort(a, mid+1, end, temp);
  49.             mc = merge(a, start, mid, end, temp);
  50.             return lc+rc+mc;
  51.         }
  52.  
  53.     }
  54.     int main()
  55.     {
  56.         int t;
  57.         cin>>t;
  58.         while(t--)
  59.         {
  60.             LL n;
  61.             cin>>n;
  62.             LL inv;
  63.             LL a[n];
  64.             LL temp[n];
  65.             for(LL i=0;i<n;i++)
  66.             {
  67.                 cin>>a[i];
  68.             }
  69.             inv = mergesort(a,0,n-1,temp);
  70.             cout<<inv<<endl;
  71.         }
  72.  
  73.         return 0;
  74.     }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
1
3
3
1
2
stdout
copy 
7
https://ideone.com/dkFw97
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!