HackerEarth Number of overtakes problem solution

In this HackerEarth Number of overtakes, problem-solution A race is organized among N horses of a kingdom. Every horse has a velocity (in m/sec) that is denoted by an array V elocity[] where Velocity[i] represents the velocity of the ith horse. The indexing of the array is 0-based.

All the horses are standing at different starting positions. The starting position of every horse is represented by an array pos[] where pos[i] denotes the starting position of the ith horse. The indexing of the array is 0-based. The pos[] array is a permutation of integers 1 to N. A horse who is standing at position is considered to be ahead of the horse who is standing at position j if and only if i > j.

The finish line of the race is 10^100000) meters ahead. An overtake occurs when horse A, whose starting position is less than horse B, finishes the race earlier than horse B. Your task is to determine the number of overtakes that has occurred during the race.

HackerEarth Number of overtakes problem solution.

#include<bits/stdc++.h>
#define ll long long int
using namespace std;

ll _mergeSort(int arr[], int temp[], int left, int right); 
ll merge(int arr[], int temp[], int left, int mid, int right); 

ll mergeSort(int arr[], int array_size) 
{ 
    int temp[array_size]; 
    return _mergeSort(arr, temp, 0, array_size - 1); 
} 
  
ll _mergeSort(int arr[], int temp[], int left, int right) 
{ 
    int mid;
    ll inv_count = 0; 
    if (right > left) { 
        /* Divide the array into two parts and  
        call _mergeSortAndCountInv()  
        for each of the parts */
        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; 
} 

ll merge(int arr[], int temp[], int left, 
          int mid, int right) 
{ 
    int i, j, k; 
    ll 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++]; 
  
            /* this is tricky -- see above  
            explanation/diagram for merge()*/
            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(){
    int N;
    cin>>N;
    assert(N >= 2 && N <= 100000);
    
    int Velocity[N];
    for(int i = 0 ; i < N ; i++)
    {
        cin>>Velocity[i];
        assert(Velocity[i] >= 1 && Velocity[i] <= 10000000);
    }

    int pos[N];
    for(int i = 0 ; i < N ; i++)
    {
        cin>>pos[i];
        assert(pos[i] >= 1 && pos[i] <= N);
    }

    int final[N];
    for(int i = 0 ; i < N ; i++)
    {
        final[pos[i]-1] = Velocity[i];
    }

    ll ans = mergeSort(final,N);
    cout<<ans<<endl;
}

Second solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

template<typename T>
struct MOS{
    tree<pair<T, int>, null_type, less<pair<T, int>>, rb_tree_tag,tree_order_statistics_node_update> os;
    map<T, int> cnt;
    int size(){
        return os.size();
    }
    int order_of_key(const T &x){
        return os.order_of_key({x, 0});
    }
    int ge(int x){
        return os.size() - order_of_key(x);
    }
    void insert(const T &x){
        os.insert({x, cnt[x]++});
    }
    void erase(const T &x){
        os.erase({x, --cnt[x]});
    }
};
MOS<int> os;
 
typedef long long ll;
 
const int maxn = 1e6 + 17;
int n;
pair<int, int> p[maxn];
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> p[i].second;
    for(int i = 0; i < n; i++)
        cin >> p[i].first;
    sort(p, p + n);
    ll ans = 0;
    for(int i = 0; i < n; i++)
        ans += os.ge(p[i].second + 1), os.insert(p[i].second);
    cout << ans << 'n';
}

coding problems solutions