Can anyone please look into my code for Euron Problem

i have seen that many accpeted codes has a temp array passed to merge function but not getting what is its use? Can someone explain what is the use of that.
https://www.codechef.com/viewsolution/32139867

#include <bits/stdc++.h>
using namespace std;

vector ar;
long long counter=0;

void merge(int l, int mid, int r) {
long long left[mid-l+1]; long long n1=mid-l+1;
long long right[r-mid]; int n2=r-mid;
int k=l;

for(int i=0;i<n1;i++)
    left[i]=ar[l+i];
for(int i=0;i<n2;i++)
    right[i]=ar[mid+i+1];   
long long i=0, j=0;
while(i<n1 && j<n2){
    if(left[i]<right[j])
        ar[k++]=left[i++];
    else{
        counter+=(n1-i);
        ar[k++]=right[j++];
    }
}
while(i<n1){
    ar[k++]=left[i++];
}
while(j<n2){
    ar[k++]=right[j++];
}

}

void merge_sort(int i, int j) {
if(i<j) {
int mid=i+(j-i)/2;
merge_sort(i, mid);
merge_sort(mid+1, j);
merge(i, mid, j);
}
}

int main() {
int n; cin >> n;
for(int i=0;i<n;i++){
long long int x; cin >> x;
ar.push_back(x);
}
merge_sort(0, n-1);
cout << counter << endl;
}

@raj_2020code Format your code first as the forum software has messed it up. Refer to the following guide by @ssjgz :

Moreover, this problem can be solved using Merge-Sort algorithm but you need to change the algorithm so that it returns the inversion count of the given sequence.

Its a pretty standard problem, so read about how to compute the inversion of an array using merge-sort from here.

You can refer to the solution in C++: Competitive-Programming/Code-Chef/Euron-Problem at master · strikersps/Competitive-Programming · GitHub

1 Like