Блог пользователя dhirajfx3

Time limit exceeded using operator () as comparator

Автор dhirajfx3, история, 8 лет назад, По-английски

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

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

http://mirror.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://mirror.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 ?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится 
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.
→ Ответить