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

Assistance for 689D
Автор miniluigi, история, 8 лет назад, По-английски

I have tried to use the Sparse Table Algorithm in order to compute the RMQ in this problem. However, this ends up timing out. I thought it was O(nlogn)?

http://codeforces.me/contest/689/submission/18959912

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

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

Auto comment: topic has been updated by miniluigi (previous revision, new revision, compare).

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

Try mend your binary search, like here and your RMQ dubious

→ Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится 
int k = floor(log(j-i+1));

Shouldn't it be log2(j — i + 1)? It would be better if you precalculate logarithms.

→ Ответить