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

Автор diegorpc, история, 6 лет назад, По-английски

Hi guys

I was solving the problem 86D — Powerful Array using Mo's algorithm. But I get TLE.

Someone can help me?

My solution

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

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

block = sqrt(n), should be block = sqrt(maxn) in this case, as you are reasoning on the frequency of each element on the array, not the array it self.

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

Also, I learnt this thing from teja349: If L1 and L2 lie in the same block, you check the parity of the block. If the parity is even, then you sort according to increasing R or else you sort according to decreasing R. This reduces runtime to half and is quite enough to get AC on this problem.

My AC submission using this trick: http://codeforces.com/contest/86/submission/28243471 (Sorry for the incredibly ill-named variables)

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

You can also try with ceil (sqrt (n)) . It worked for me . @gaurav172 taught me this .