dhirajfx3's blog

Time limit exceeded using operator () as comparator

By dhirajfx3, history, 7 years ago, In English

In solution of http://codeforces.com/problemset/problem/375/D

consider struct qry { int l,r,id,val; int block; }; vector<qry> Q; vector<int> q_idx;

http://codeforces.com/contest/375/submission/26098047 this solution got AC , it used

sort(Q.begin(),Q.end(),[](qry &A,qry &B)
{  
       if( A.block == B.block )
		return A.r < B.r;
	return A.block < B.block;	
});

whereas

http://codeforces.com/contest/375/submission/26097714 this solution got TLE using

bool operator()(int x,int y) 
{
	if( Q[x].block == Q[y].block )
		return Q[x].r < Q[y].r;
	return Q[x].block < Q[y].block;	
}
sort(q_idx.begin(),q_idx.end(),*this); // q_idx is vector<int> containing indices

Can anyone explain why this happened ?

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

»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it 
sort(..... ,  *this); 
  //           ^
//             |
//            copied a many times your MoAlgo class with vectors.

// use:
sort( .....,  [this](int x, int y){  return (*this)(x,y); } ) ; // there copied pointer to MoAlgo class.
→ Reply