HackerEarth Suarez problem solution

In this HackerEarth Suarez! problem solution You are given N segments [L, R], where L <= R . Now, you need to answer some queries based on these segments.

Overall, you need to answer Q queries. In each query you shall be given 2 integers K and X. You need to find the size of the Kth smallest segment that contains point X.

If no K segments contain point X, print 1 instead as the answer to that query.

A segment [L, R] is said to contain a point X if L <= X <= R. When we speak about the Kth smallest segment, we refer to the one having the Kth smallest size. We define the size of a segment to be the number of integral points it contains, i.e. R + 1 – L

import java.io.*;
import java.util.*;
import java.math.*;

public final class solution
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
    static Random rnd=new Random();
    static Pair[] a,b;
    static Pair[][] al,qr;
    static int[] size,c1,c2;
    static int[] bit,cnt,res;
    static int maxn=(int)(1e6+6);
    
    static void update(int idx,int val)
    {
        while(idx<maxn)
        {
            bit[idx]+=val;idx+=idx&-idx;
        }
    }
    
    static int query(int idx)
    {
        int ret=0;
        
        while(idx>0)
        {
            ret=ret+bit[idx];idx-=idx&-idx;
        }
        
        return ret;
    }
    
    static void shuffle(int[] a)
    {
        for(int i=0;i<a.length;i++)
        {
            int next=rnd.nextInt(a.length);
            
            int temp=a[i];a[i]=a[next];a[next]=temp;
        }
    }
    
    public static void main(String args[]) throws Exception
    {
        int n=sc.nextInt();a=new Pair[n];size=new int[n];c2=new int[n];
        
        if(n<1 || n>200000) throw new Exception("Wrong!");
        
        for(int i=0;i<n;i++)
        {
            a[i]=new Pair(sc.nextInt(),sc.nextInt());
            
            size[i]=a[i].r-a[i].l+1;c2[i]=size[i];
            
            if(a[i].l<1 || a[i].r>(int)1e9 || a[i].l>a[i].r) throw new Exception("Wrong!");
        }
        
        int q=sc.nextInt();b=new Pair[q];c1=new int[n+n+q];int j=0;
        
        if(q<1 || q>200000) throw new Exception("Wrong!");
        
        for(int i=0;i<q;i++)
        {
            b[i]=new Pair(sc.nextInt(),sc.nextInt());
            
            c1[j++]=b[i].r;
            
            if(b[i].l<1 || b[i].l>n || b[i].r<1 || b[i].r>(int)(1e9)) throw new Exception("Wrong!");
        }
        
        for(int i=0;i<n;i++)
        {
            c1[j++]=a[i].l;c1[j++]=a[i].r;
        }
        
        shuffle(c1);shuffle(c2);Arrays.sort(c1);Arrays.sort(c2);cnt=new int[maxn];
        
        for(int i=0;i<n;i++)
        {
            a[i].l=Arrays.binarySearch(c1,a[i].l);
            
            a[i].r=Arrays.binarySearch(c1,a[i].r);
            
            size[i]=Arrays.binarySearch(c2,size[i])+1;
            
            cnt[a[i].l]++;cnt[a[i].r+1]++;
        }
        
        al=new Pair[maxn][];
        
        for(int i=0;i<maxn;i++)
        {
            al[i]=new Pair[cnt[i]];cnt[i]=0;
        }
        
        for(int i=0;i<n;i++)
        {
            int curr1=a[i].l,curr2=a[i].r+1;
            
            al[curr1][cnt[curr1]++]=new Pair(size[i],1);
            
            al[curr2][cnt[curr2]++]=new Pair(size[i],-1);
        }
        
        qr=new Pair[maxn][];Arrays.fill(cnt,0);
        
        for(int i=0;i<q;i++)
        {
            b[i].r=Arrays.binarySearch(c1,b[i].r);
            
            cnt[b[i].r]++;
        }
        
        for(int i=0;i<maxn;i++)
        {
            qr[i]=new Pair[cnt[i]];cnt[i]=0;
        }
        
        for(int i=0;i<q;i++)
        {
            int curr=b[i].r;
            
            qr[curr][cnt[curr]++]=new Pair(i,b[i].l);
        }
        
        bit=new int[maxn];res=new int[q];
        
        for(int i=0;i<maxn;i++)
        {
            for(Pair x:al[i])
            {
                update(x.l,x.r);
            }
            
            for(Pair x:qr[i])
            {   
                int k=x.r,low=1,high=maxn-1;
                
                while(low<high)
                {
                    int mid=(low+high)>>1;
                    
                    if(query(mid)>=k)
                    {
                        high=mid;
                    }
                    else
                    {
                        low=mid+1;
                    }
                }
                
                res[x.l]=query(low)>=k?low:-1;
            }
        }
        
        for(int i=0;i<q;i++)
        {
            int ans=res[i];
            
            ans=ans==-1?ans:c2[ans-1];
            
            out.println(ans);
            
            if(ans==0 || ans<-1 || ans>(int)(1e9)) throw new Exception("Wrong!");
        }
        
        out.close();
    }
}

class Pair implements Comparable<Pair>
{
    int l,r;
    
    public Pair(int l,int r)
    {
        this.l=l;this.r=r;
    }
    
    public int compareTo(Pair x)
    {
        return Integer.compare(this.r-this.l+1,x.r-x.l+1);
    }
}

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());
    }
}