HackerEarth Vanya and Array problem solution

In this HackerEarth Vanya and Array problem solution Let’s define 2 functions a function F(i) and Val(i,j) for an Array A of size N as follows:

F(i) = Sigma(j=i+1, N) Val(i,j)

Val(i,j) = 1 ,if A[i] < A[j], else, Val(i,j) = 0.

Now, Vanya has been given one such array A of size N and an integer K. She needs to find the number of Distinct Unordered Pairs of elements (a,b) in array A such that F(a) + F(b) >= K.

HackerEarth Vanya and Array problem solution.

import java.io.*;
import java.util.*;
public final class vanya_and_array
{
    static long[] bit;
    static int maxn=1000015;
    static FastScanner sc=new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out=new PrintWriter(System.out);
    
    static void update(int idx)
    {
        while(idx<maxn)
        {
            bit[idx]++;
            idx+=idx&-idx;
        }
    }
    
    static long query(int idx)
    {
        long sum=0;
        while(idx>0)
        {
            sum=sum+bit[idx];
            idx-=idx&-idx;
        }
        return sum;
    }
    
    public static void main(String args[]) throws Exception
    {
        int n=sc.nextInt(),k=sc.nextInt();
        int[] a=new int[n],b=new int[n];bit=new long[maxn];
        for(int i=0;i<n;i++)
        {
            a[i]=sc.nextInt();
            b[i]=a[i];
        }
        Arrays.sort(b);
        for(int i=0;i<n;i++)
        {
            a[i]=Arrays.binarySearch(b,a[i])+1;
        }
        long[] val=new long[n];
        for(int i=n-1;i>=0;i--)
        {
            val[i]=query(maxn-1)-query(a[i]);
            update(a[i]);
        }
        Arrays.sort(val);
        long res=0;
        for(int i=n-1;i>0;i--)
        {
            int low=1,high=i;
            while(low<high)
            {
                int mid=(low+high+1)>>1;
                if(val[i]+val[i-mid]>=k)
                {
                    low=mid;
                }
                else
                {
                    high=mid-1;
                }
            }
            if(val[i]+val[i-low]>=k)
            {
                res=res+((i-1)-(i-low)+1);
            }
        }
        out.println(res);
        out.close();
    }
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
    
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
    
    public String next() throws Exception {
        return nextToken().toString();
    }
    
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}

Second solution

#include<bits/stdc++.h>
using namespace std;
int getSum(int BITree[], int index)
{
    int sum = 0;
    while (index > 0)
    {
        sum += BITree[index];
        index -= index & (-index);
    }
    return sum;
}
void updateBIT(int BITree[], int n, int index, int val)
{
    while (index <= n)
    {
       BITree[index] += val;
       index += index & (-index);
    }
}
void convert(int arr[], int n)
{
    int temp[n];
    for (int i=0; i<n; i++)
        temp[i] = arr[i];
    sort(temp, temp+n);int i;
    for (i=0; i<n; i++)
    {
        arr[i] = lower_bound(temp, temp+n, arr[i]) - temp + 1;
    arr[i]=n-arr[i]+1;  //changing largest element as smallest and so on, later we need to apply simple inversion count
    }
}
int f[1000005];
void getInvCount(int arr[], int n)
{
    int invcount = 0;
    convert(arr, n);
    int BIT[n+1];
    for (int i=1; i<=n; i++)
        BIT[i] = 0;
    for (int i=n-1; i>=0; i--)
    {
        
    f[i]= getSum(BIT, arr[i]-1);
        updateBIT(BIT, n, arr[i], 1);
    }
}
int main()
{
    int n,k,i,a[1000005];
    scanf("%d%d",&n,&k);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    getInvCount(a,n);
    sort(f,f+n);long long count=0;
    vector<int>v(f,f+n);
    for(i=n-1;i>=0;i--)
    {
        int j=lower_bound(v.begin(),v.end(),k-v[i])-v.begin();
        if(j!=n && j<i)
            count+=i-j;
    }
    printf("%lldn",count);
    return 0;
}

coding problems solutions