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

Katy Brute force;-) [4] // Задача 1126. Магнитные бури 21 июл 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] // Задача 1126. Магнитные бури 22 июл 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;-) // Задача 1126. Магнитные бури 1 ноя 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;-) // Задача 1126. Магнитные бури 3 ноя 2006 10:29

My solution is O(N).

Ealham No subject // Задача 1126. Магнитные бури 20 мар 2016 19:04

Katy писал(a) 21 июля 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

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