### kth smallest segment containing a number

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?
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.
 ``123456789101112131415161718192021222324252627282930313233343536373839404142`` ``````#include #include #include using namespace std; int main() { int n,x,y; cin>>n; //no of input pair>p[n]; //size of segment, first no, second no for(int i=0;i>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>x>>y; //input k and x of ques int cnt=0,ans=-1,flag=0; //to get accurate answer for(int j=0;j=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<

I also tried using precomputed values but mle

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051`` ``````#include #include #include #include #include using namespace std; int main() { int n,x,y; cin>>n; pair>p[n]; map>m; for(int i=0;i>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>x>>y; if(m[y].size()>=x) { cout<=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<
Last edited on
> 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".
I am getting so many memory limit exceeded. It's strange.
 ``1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071`` ``````#include #include #include #include using namespace std; void findrange(int y,map>&m,pairp[],int low,int high) { //cout<=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(paira,pairb) { if(a.first>n; pairp[n]; //size,first,second for(int i=0;i>x>>y; p[i].first=x; p[i].second=y; } sort(p,p+n,cond); map>m; //no,size int query; cin>>query; for(int i=0;i>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<