Tobby_And_Friends's blog

By Tobby_And_Friends, history, 8 months ago, In English,

Problem link: http://www.spoj.com/problems/ADAUNIQ/

My solution: https://ideone.com/srH91b

Verdict: TLE

How do I optimize my solution? Any help is really appreciated.

[Update] Got AC :) I missed out the fact that block sizes are of n^(2/3)

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You're not supposed to compare right ends by buckets, instead, just compare values. So, replace if(r1 != r2) return r1 < r2; with if(a.r != b.r) return a.r < b.r;

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If you wish to know how to use Mo's algorithm with updates, check out this blog post, but I doubt that it will be fast enough.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thank You :)

  • »
    »
    8 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks a ton :) I understood where I was wrong logically. Got AC now :)

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Good job! There is also a online solution.

      Hint
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Though you got AC, I'd like to mention one more thing.
I see you wrote —

int l1 = a.l/SZ, l2 = b.l/SZ;
int r1 = a.r/SZ, r2 = b.r/SZ;

This might be the reason of your getting TLE. I got 2-3 times too.
Instead of doing this, precompute block numbers and do —

int l1 = blc[a.l], l2 = blc[b.l];
......

This will significantly reduce your run time.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can it be solved using offline BIT in something like O(nlg2(n)) just like the one without updates (DQUERY)?