|
|
back to boardShow all messages Hide all messagesI'm calculating for every interval the max element with binary indexed tree in log(n) time. But still got TL on test 2. Is it ok NlogM to be slow ? It can be solved in O(NM), TLE is too big. Once my friend did it :) I think there's a bug in your implementation. Are you sure that (build a tree on i-th step) + (find element) works in O(NlogM)? I used two stacks (they works like queue) with access to max element in O(1) (something like 3 operations on each element). So it can be solved in O(n)! |
|
|