Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### codeofthrone's blog

By codeofthrone, history, 3 months ago, ,

In each query, I have to insert x in a vector so that it remains sorted and output the Yth element. Inserting was taking O(n) time.

I switched to multiset as it remains sorted on each insertion with O(log(n)) time but I am stuck in finding the Yth element. The only approach worked was to traverse the multiset from starting but again it gives TLE.

I searched the internet but couldn't found anything relevant. Is there any way to access the ith indexed element in multiset in O(log(n) ) time.

Consider I am using C++.

• +6

By codeofthrone, history, 3 months ago, ,

Is it possible to to have a custom comparator function for priority queue which keeps on changing. If not is their any way to implement this functionality. Ex:

#define fi first
#define se second

int X,Y;
struct comp
{
bool operator()(pair<int,int>& A, pair<int,int> & B)
{
int x1=A.fi,y1=A.se,x2=B.fi,y2=B.se;
if((abs(X-x1)+abs(Y-y1))>(abs(X-x2)+abs(Y-y2)))
{
return false;
}
else
return true;
}

};


////in MAin

 X=1,Y=1;
priority_queue<pair<int,int>, vector<pair<int,int>  >,comp>PQ;
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{
if(i==1 && j==1) continue;
PQ.push(m_p(i,j));
}
}
cout<<1<<" "<<1<<endl;
while(!PQ.empty())
{
int x=PQ.top().fi;
int y=PQ.top().se;
cout<<x<<" "<<y<<endl;
PQ.pop();
X=x;Y=y;
}


as we keep on changing X,Y, our PQ will change itself accordingly?