fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std ;
  3. long long int temp[200000] ; 
  4. long long int a[200000] ; 
  5. long long inversioncount( int s , int e ){
  6.     // Handling the base case of the recursive function 
  7.     if(s==e) return 0 ; // one element no need to sort and no inversion 
  8.     if(s==e-1){
  9.         // two elements either one inversion or no inversion 
  10.         if(a[s] <= a[e] ) return 0 ; 
  11.         else{
  12.             swap(a[s] , a[e] );
  13.             return 1 ; 
  14.         }
  15.     }
  16.     int mid = (s+e)/2 ; 
  17.     long long ans =  0 ; 
  18.     // adding contribution to inversion from right and left subarray
  19.     ans += inversioncount(  s , mid ) ;
  20.     ans += inversioncount(  mid+1 , e ) ; 
  21.     int l = s , r = mid+1 , k = s; 
  22.  
  23.     // merging and caluclating remaining inversions 
  24.     while(l<=mid and r<=e){
  25.         if(a[l]<=a[r]){
  26.             // no inversion simply add the element 
  27.             temp[k] = a[l] ; 
  28.             l ++ ; k ++ ; 
  29.         }else{
  30.             // inversions! add element to temp array and reflect inversions in final answer
  31.             temp[k] = a[r] ; 
  32.             r ++ ; k++ ; 
  33.             ans += mid - l  + 1 ; 
  34.         }
  35.     }
  36.     //Handle left over elements from the two arrays as in case of merge sort 
  37.     while(l<=mid){
  38.         temp[k] = a[l] ; 
  39.         l ++ ; k ++ ; 
  40.     }
  41.     while(r<=e){
  42.             temp[k] = a[r] ; 
  43.             r ++ ; k++ ; 
  44.     }
  45.     // copy sorted elements back from the sorted temp array to the original array
  46.     for(int i = s ; i <= e ; i ++ ){
  47.         a[i] = temp[i] ; 
  48.     }
  49.  
  50.     return ans ; 
  51. }
  52. void solve(){
  53.     //getchar() ; 
  54.     int n ;
  55.     cin >> n ; 
  56.     for( int i = 0 ; i < n ; i  ++){
  57.         cin >> a[i] ; 
  58.     }
  59.     cout << inversioncount( 0 , n-1) << "\n" ;
  60. }
  61. int main(){
  62.     #ifndef ONLINE_JUDGE
  63.     freopen("input.txt","r",stdin);
  64.     freopen("output.txt","w",stdout);
  65.     #endif
  66.  long long  tc ; 
  67.  cin >> tc ;
  68.  while(tc--){
  69.  solve() ;
  70.  } 
  71. return 0;
  72. }
  73.  
Success #stdin #stdout 0.01s 5568KB
comments (?)
stdin
copy 
2

3
3
1
2

5
2
3
8
6
1
stdout
copy 
2
5
https://ideone.com/AjZTIE
language:
C++14 (gcc 8.3)
created:
3 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!