Time limit exceeded using operator () as comparator

Revision en1, by dhirajfx3, 2017-04-03 15:43:07

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 ?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English dhirajfx3 2017-04-03 15:43:07 836 Initial revision (published)