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

Getting TLE in MO's Algorithm with updates [SPOJ ADAUNIQ — Ada and Unique Vegetable]
Автор Tobby_And_Friends, история, 6 лет назад, По-английски

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)

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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;

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить