ANITGUY3 - Editorial

Problem: Contest Page | CodeChef

DIFFICULTY:

EASY.

PROBLEM:

The chef has one array of N natural numbers (might be in sorted order). Cheffina challenges chef to find the total number of inversions in the array.

Program:

#include<bits/stdc++.h> 
using namespace std; 
long long _mergeSort(int arr[], int temp[],  
                 int left, int right); 
long long merge(int arr[], int temp[], int left,  
                   int mid, int right); 
long long mergeSort(int arr[], int array_size) 
{ 
    int temp[array_size]; 
    return _mergeSort(arr, temp, 0, array_size - 1); 
} 
long long _mergeSort(int arr[], int temp[],  
                 int left, int right) 
{ 
    long long mid, inv_count = 0; 
    if (right > left) { 
        mid = (right + left) / 2; 
        inv_count += _mergeSort(arr, temp,  
                                left, mid); 
        inv_count += _mergeSort(arr, temp,  
                             mid + 1, right); 
        inv_count += merge(arr, temp, left,  
                           mid + 1, right); 
    } 
    return inv_count; 
} 
long long merge(int arr[], int temp[], int left, 
          int mid, int right) 
{ 
    int i, j, k; 
    long long inv_count = 0; 
  
    i = left; /* i is index for left subarray*/
    j = mid; /* j is index for right subarray*/
    k = left; /* k is index for resultant merged subarray*/
    while ((i <= mid - 1) && (j <= right)) { 
        if (arr[i] <= arr[j]) { 
            temp[k++] = arr[i++]; 
        } 
        else { 
            temp[k++] = arr[j++]; 
            inv_count = inv_count + (mid - i); 
        } 
    } 
    while (i <= mid - 1) 
        temp[k++] = arr[i++]; 
    while (j <= right) 
        temp[k++] = arr[j++]; 
    for (i = left; i <= right; i++) 
        arr[i] = temp[i]; 
    return inv_count; 
} 
int main() 
{ 
	ios_base::sync_with_stdio(false);
   	cin.tie(NULL);
   	cout.tie(NULL);
   	int t;
   	cin>>t;
   	while(t--){
   		int n;
   		cin>>n;
   		int arr[n];
   		for(int i=0;i<n;i++)cin>>arr[i];
   		cout<<mergeSort(arr,n)<<"\n";
   	}
}