Help Needed in Mo's Algo

1

Obviously after the recent long challenge, I was trying to implement Mos Algo.

I used the following comparator,

struct query
{
    ll l,r,idx;
    
    query(ll _l , ll _r , ll _idx) : l(_l) , r(_r) , idx(_idx) {} 
 
    bool operator < (const query& myquery)
    {
        if( l/block_size != myquery.l/block_size) 
            return l/block_size < myquery.l/block_size;
        else
            return r <= myquery.r ;                   
    }
};

This runs into a runtime error.

While this works fine

struct query
{
    ll l,r,idx;
    
    query(ll _l , ll _r , ll _idx) : l(_l) , r(_r) , idx(_idx) {} 

    bool operator < (const query& myquery)
    {
        return mp(l/block_size,r) < mp(myquery.l/block_size,myquery.r);                  
    }
};

Why is this?

2

Remove the equal sign from the comparator and it would work.

Basically comparator function is used for ordering of elements of the data structure. You return true if you want a to come before b. In the case when both are equal , you are returning true which means that a should come before b and also b should come before a. Which is simply not possible. So it is showing Runtime Error.

6 Likes