fork download 
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. long long Merge(long long * a, long long l, long long mid, long long n){
  5.      long long p=l,q=mid,i=0,c=0;
  6.      long long tmp[n-l+1];
  7.      while(p<mid && q<=n){
  8.           if(a[p]<=a[q])
  9.                tmp[i++]=a[p++];
  10.           else{
  11.                tmp[i++]=a[q++];
  12.                c+=mid-p;
  13.           }
  14.      }
  15.      while(p<mid)
  16.           tmp[i++]=a[p++];
  17.      while(q<=n)
  18.           tmp[i++]=a[q++];
  19.      long long j=0;
  20.     while(l<=n)
  21.           a[l++]=tmp[j++];
  22.      return c;
  23. }
  24.  
  25. long long MergeSort(long long * a, long long b, long long n){
  26.      long long mid,c=0;
  27.      if(b<n){
  28.           mid=(b+n)/2;
  29.           c+=MergeSort(a,b,mid);
  30.           c+=MergeSort(a,mid+1,n);
  31.           c+=Merge(a,b,mid+1,n);
  32.      }
  33.      return c;
  34. }
  35. int main()
  36. {
  37.      long long n;
  38.      while(cin>>n && n!=0){
  39.           long long a[n];
  40.           for(int i=0;i<n;i++)
  41.                cin>>a[i];
  42.           cout<<MergeSort(a,0,n-1)<<"\n";
  43.           //for(int i=0;i<n;i++)
  44.              //  cout<<a[i]<<" ";
  45.          // cout<<"\n";
  46.      }
  47. }
  48.  
Success #stdin #stdout 0s 3148KB
comments (?)
stdin 
5
9
1
0
5
4
3
1
2
3
0
stdout 
6
0
https://ideone.com/iMsTVV
language:
C++14 (gcc 8.3)
created:
10 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!