miniluigi's blog

Assistance for 689D
By miniluigi, history, 8 years ago, In English

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://mirror.codeforces.com/contest/689/submission/18959912

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

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

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it 
int k = floor(log(j-i+1));

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

→ Reply