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

codeofthrone's blog

By codeofthrone, history, 3 months ago, In English,

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++.

Thanks in advance.

Read more »

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

By codeofthrone, history, 3 months ago, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it