|
|
вернуться в форумTL on test 2; O( (n-m)*log m ), is O(n logm) slow ? I'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 ? Re: TL on test 2; O( (n-m)*log m ), is O(n logm) slow ? Послано Noob 2 окт 2011 00:18 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. Re: TL on test 2; O( (n-m)*log m ), is O(n logm) slow ? 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)! |
|
|
