Mo's algo sort function differences.

Revision en12, by mbstu_nitai, 2018-07-26 22:11:41

=====================================================================

What are the differences between this three sort functions in Mo's algo?

First approach:

bool comp(stt q1, stt q2)
{
    int block_a = q1.l / sq, block_b = q2.l / sq;
    if(block_a == block_b)
        return q1.r < q2.r;
    return block_a < block_b;
}

Second approach:

bool comp(stt q1, stt q2)
{
  if (q1.l / sq != q2.l / sq) return q1.l< q2.l;
  return (q1.r < q2.r)^(q1.l/sq%2);
}

Third approach:

bool comp(stt q1, stt q2)
{
    if(q1.l/sq != q2.l/sq)
    {
        return q1.l < q2.l;
    }
    if((q1.l/sq) & 1)
    {
        return q1.r < q2.r;
    }
    return q1.r > q2.r;
}

Problem link

The first approach gives the TLE on test 9 Submission linkthe second approach gives the TLE on test 67 Submission linkbut the third approach gives AC Submission link. Thanks in advance. :)

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en15 English mbstu_nitai 2018-07-31 16:25:38 7 Tiny change: '2.l / sq) return q1' -> '2.l / sq) \n return q1'
en14 English mbstu_nitai 2018-07-27 01:28:02 1 Tiny change: 'ssion link](https://' -> 'ssion link ](https://'
en13 English mbstu_nitai 2018-07-27 01:25:30 2
en12 English mbstu_nitai 2018-07-26 22:11:41 2 Tiny change: 'ance. :)\n\n' -> 'ance. :)\n'
en11 English mbstu_nitai 2018-07-26 16:41:45 1 Tiny change: 't function in Mo's a' -> 't functions in Mo's a'
en10 English mbstu_nitai 2018-07-26 09:32:57 12
en9 English mbstu_nitai 2018-07-26 09:30:09 64
en8 English mbstu_nitai 2018-07-25 23:15:16 1 Tiny change: ' advance. v:)\n\n' -> ' advance. :)\n\n'
en7 English mbstu_nitai 2018-07-25 23:07:53 2
en6 English mbstu_nitai 2018-07-25 22:42:11 6
en5 English mbstu_nitai 2018-07-25 22:41:21 436
en4 English mbstu_nitai 2018-07-25 21:38:00 148
en3 English mbstu_nitai 2018-07-25 21:34:06 2 Tiny change: 'Second**\n\nbool com' -> 'Second**\nbool com'
en2 English mbstu_nitai 2018-07-25 21:33:41 41
en1 English mbstu_nitai 2018-07-25 21:32:11 742 Initial revision (published)