# 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

## 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;}`