ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

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

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

It can be solve in O(N+M) Ted 7 май 2004 13:08
Can you tell more about this solution? A new start... 7 май 2004 18:39
I'm not good at English.

A[I] is the Ith number.

First,try to count a array F.

F[I] means the nearest number A[F[I]]:
A[F[I]]>A[I] and F[I]>I.

You can count F in O(N).

Find largest number in [L,R],just find a min I,F[I]>R.

So you can solve the problem in O(N+M).

And this problem is RMQ problem, also have a very hard standard solution in O(N+M).

Edited by author 07.05.2004 20:31
strong!
Good idea. But I had to be very carefully solving it.

Edited by author 04.05.2006 20:00
Thanks, @Ted.
Your idea is brilliant.
I count F[] array with O(N) , used stack.
+  buffered i/o ==> result is very good: AC. 0.001s
Re: It can be solve in O(N+M) Partisan 20 май 2006 19:48
There is an interesting situation here: when I declared arrays a and f with size 1..25000, I got WA#2. When I changed them to 1..25001, I got AC...
Re: It can be solve in O(N+M) BlindButcher 22 окт 2008 17:47
I have used rather simple method, I have organized four stacks, first two to make a queue of M size, and others to store max elements of queue, by this way you can find elements in constant time. Very useful for Java, you have Class Stack.
Re: It can be solve in O(N+M) Ealham 20 мар 2016 18:58
BlindButcher писал(a) 22 октября 2008 17:47
I have used rather simple method, I have organized four stacks, first two to make a queue of M size, and others to store max elements of queue, by this way you can find elements in constant time. Very useful for Java, you have Class Stack.

Thanks for sharing the idea...
:)