Обсуждение @ 1126. Магнитные бури @ Timus Online Judge

Показать все сообщения Спрятать все сообщения

TL on test 2; O( (n-m)*log m ), is O(n logm) slow ? cs_Diablo 1 окт 2011 22:49

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 ? MOPDOBOPOT (USU) 31 июл 2012 21:06

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)!

Обсуждение задачи 1126. Магнитные бури