Discussion @ 1126. Magnetic Storms @ Timus Online Judge

Katy Brute force;-) [4] // Problem 1126. Magnetic Storms 21 Jul 2006 03:52

I know that this problem could be solved using sorting and something like that - my friends do so but don't share code, I don't know how.
I used brute force (= the easiest way) and i got AC 0.281 330 KB at C++

N.M.Hieu ( DHSP ) Re: Brute force;-) [2] // Problem 1126. Magnetic Storms 22 Jul 2006 09:54

You can use structure Heap or Interval Tree ( because the value of the elements is rather small ).
Heap : O(NlogM)
Interval tree : O(N log(Max_Value) ).
Interval tree also can give you the k-th smallest value in log (Max_value).

The Ninjas Walk Alone!!!! Re: Brute force;-) // Problem 1126. Magnetic Storms 1 Nov 2006 14:25

And I've wrote it with maximizator in O(m*log(n)).

You can read about this and many other structures in this lecture: http://zorg-n-ko.nm.ru/lecture.html

UdSU: Ajtkulov, Kotegov, Saitov Re: Brute force;-) // Problem 1126. Magnetic Storms 3 Nov 2006 10:29

My solution is O(N).

Ealham No subject // Problem 1126. Magnetic Storms 20 Mar 2016 19:04

Katy wrote 21 July 2006 03:52

Yes... and with little bit of optimization, one can get AC in half of that time... :)

Edited by author 20.03.2016 19:06

Discussion of Problem 1126. Magnetic Storms