kth smallest segment containing a number

[1vf9z8AR]

Question-
https://www.hackerearth.com/practice/data-structures/trees/binary-search-tree/practice-problems/algorithm/suarez/description/

Issue-
Solved using pairs, vectors, maps but all the methods give tle or mle. Can you tell me the method to solve this one?

[salem c]

Well you use those things.

You just have to be smarter as to how you use them.

If you posted your code, perhaps we could tell you where you're being particularly inefficient.

[1vf9z8AR]

#include<iostream>
#include<algorithm>
#include<utility>
using namespace std;
int main()
{
    int n,x,y;
    cin>>n;                                //no of input
    pair<int,pair<int,int>>p[n];  //size of segment, first no, second no
    for(int i=0;i<n;i++)
    {
        cin>>x>>y;                      // first no, second no
        p[i].first=y-x;  //size of segment
        p[i].second.first=x;  //first no
        p[i].second.second=y; //second no
    }
    sort(p,p+n);  //sort by segment size
    int q;
    cin>>q;  //no of query
    for(int i=0;i<q;i++)
    {
        cin>>x>>y;    //input k and x of ques
        int cnt=0,ans=-1,flag=0;   //to get accurate answer
        for(int j=0;j<n;j++)
        {
            if(y>=p[j].second.first && y<=p[j].second.second)    //check in segment
            {
                cnt++;
                if(cnt==x)                                          //found kth segment containing the no
                {
                    ans=p[j].first+1;
                    flag=1;
                    break;
                }
            }
            if(flag==1)
                break;
        }
        cout<<ans<<endl;   //output answer
    }
    return 0;
}

I also tried using precomputed values but mle

#include<iostream>
#include<algorithm>
#include<map>
#include<utility>
#include<vector>
using namespace std;
int main()
{
    int n,x,y;
    cin>>n;
    pair<int,pair<int,int>>p[n]; 
    map<int,vector<int>>m;
    for(int i=0;i<n;i++)
    {
        cin>>x>>y;
        p[i].first=y-x;  //size of segment
        p[i].second.first=x;  //first no
        p[i].second.second=y; //second no
    }
    sort(p,p+n);  //sort by segment size
    int q;
    cin>>q;
    for(int i=0;i<q;i++)
    {
        cin>>x>>y;
        if(m[y].size()>=x)
        {
            cout<<m[y][x-1]+1<<endl;
            continue;
        }
        int cnt=0,ans=-1,flag=0;
        for(int j=0;j<n;j++)
        {
            if(y>=p[j].second.first && y<=p[j].second.second)
            {
                cnt++;
                m[y].push_back(p[j].first);
                if(cnt==x)
                {
                    ans=p[j].first+1;
                    flag=1;
                    break;
                }
            }
            if(flag==1)
                break;
        }
        cout<<ans<<endl;
    }
    return 0;
}

[salem c]

> for(int j=0;j<n;j++)
Well the point of doing a sort() is that you no longer need to do a linear search.

The hint is in the title - "binary search".

[1vf9z8AR]

I am getting so many memory limit exceeded. It's strange.

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
void findrange(int y,map<int,vector<long long int>>&m,pair<int,int>p[],int low,int high)
{
    //cout<<low<<" "<<high<<endl;
    if(low<=high)
    {
        int mid=low+(high-low)/2;
        
        if(y>=p[mid].first && y<=p[mid].second)
        {
            m[y].push_back(p[mid].second-p[mid].first+1);
            findrange(y,m,p,mid+1,high);
            findrange(y,m,p,low,mid-1);
        }
        else if(y>p[mid].first)
        {
            findrange(y,m,p,mid+1,high);
        }
        else
        {
            findrange(y,m,p,low,mid-1);
        }
    }
}
bool cond(pair<int,int>a,pair<int,int>b)
{
    if(a.first<b.first)
        return true;
    if(a.first==b.first)
    {
        if(a.second<b.second)
            return true;
    }
    return false;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,x,y;
    cin>>n;
    pair<int,int>p[n]; //size,first,second
    for(int i=0;i<n;i++)
    {
        cin>>x>>y;
        p[i].first=x;
        p[i].second=y;
    }
    sort(p,p+n,cond);
    map<int,vector<long long int>>m; //no,size
    int query;
    cin>>query;
    for(int i=0;i<query;i++)
    {
        cin>>x>>y;
        if(m[y].size()==0)
        {
            findrange(y,m,p,0,n-1);     //binary search 
            sort(m[y].begin(),m[y].end());
            
        }
        if(m[y].size()>=x)
            cout<<m[y][x-1]<<endl;
        else
            cout<<-1<<endl;
    }
}