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


HackerEarth Suarez ! problem solution


HackerEarth Suarez! problem solution.

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

Second solution

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <cstring>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
const int MAXN = 200005;
unordered_map <int,int> M;
vector <int> que[MAXN];
vector <pip> intervals;
int l[MAXN], r[MAXN], k[MAXN], x[MAXN], lo[MAXN], hi[MAXN], mid[MAXN], BIT[3*MAXN];
void BIT_upd(int pos, int val)
{
    while(pos < 3*MAXN)
    {
        BIT[pos]+=val;
        pos+=(pos & (-pos));
    }
}
int BIT_get(int pos)
{
    int ret = 0;
    while(pos > 0)
    {
        ret+=BIT[pos];
        pos-=(pos & (-pos));
    }
    return ret;
}
int main()
{
    int n;
    scanf("%d", &n);
    vector <int> nums;
    for (int i = 0; i < n; ++i)
    {
        scanf("%d %d", &l[i], &r[i]);
        nums.push_back(l[i]);
        nums.push_back(r[i]);
    }
    int q;
    scanf("%d", &q);
    for (int i = 0; i < q; ++i)
    {
        scanf("%d %d", &k[i], &x[i]);
        nums.push_back(x[i]);
    }
    sort(nums.begin(), nums.end());
    nums.resize(unique(nums.begin(), nums.end()) - nums.begin());
    for (int i = 0; i < nums.size(); ++i)
    {
        M[nums[i]] = i + 1;
    }
    for (int i = 0; i < n; ++i)
    {
        intervals.push_back(pip(r[i] + 1 - l[i], pii(M[l[i]],M[r[i]])));
    }
    sort(intervals.begin(), intervals.end());
    for (int i = 0; i < q; ++i)
    {
        lo[i] = 0;
        hi[i] = n;
        mid[i] = (lo[i] + hi[i])/2;
        que[mid[i]].push_back(i);
    }
    bool changed = true;
    while(changed)
    {
        changed = false;
        memset(BIT, 0, sizeof BIT);
        for (int i = 0; i < n; ++i)
        {
            int l = intervals[i].second.first, r = intervals[i].second.second;
            BIT_upd(l,1);
            BIT_upd(r+1,-1);
            while(!que[i].empty())
            {
                int qnum = que[i].back();
                que[i].pop_back();
                int pos = M[x[qnum]];
                if(BIT_get(pos) >= k[qnum])
                    hi[qnum] = mid[qnum];
                else
                    lo[qnum] = mid[qnum] + 1;
                if(lo[qnum] < hi[qnum])
                {
                    changed = true;
                    mid[qnum] = (lo[qnum] + hi[qnum])/2;
                    que[mid[qnum]].push_back(qnum);
                }
            }
        }
    }
    for (int i = 0; i < q; ++i)
    {
        if(lo[i] >= n)
            printf("-1\n");
        else
            printf("%d\n", intervals[lo[i]].first);
    }
    return 0;
}