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

Обсуждение задачи 1019. Перекрашивание прямой

I got accepted using O(n^2) algo. Who can do O(n*log(n))?
Послано KRSU 2 4 мар 2005 18:27
when i ignored tests where ai=bi,
I got accepted. I used O(n^2) algo.

Is it possible to solve problem in O(n*log(n))?
If so, please give me idea how to do it.
thanks.
Re: I got accepted using O(n^2) algo. Who can do O(n*log(n))?
Послано b4die 19 июл 2005 09:09
we can use segment tree to solve this problem.
every point we can save the continutely segement's length.
then solve the problem in n*logn.
Re: I got accepted using O(n^2) algo. Who can do O(n*log(n))?
Послано tyzwsai 27 июл 2007 08:17
use segment tree
Re: I got accepted using O(n^2) algo. Who can do O(n*log(n))?
Послано LiuKe 24 ноя 2007 08:45
How did you accept using O(n^2)??
I can't believe!
I think it must be solved with O(n log n) or (n*sqrt(n))!
Re: I got accepted using O(n^2) algo. Who can do O(n*log(n))?
Послано Rudolf 15 июл 2008 06:05
Why you ignore tests where ai == bi/ for example:

3
1 999999999 b
2 10 w
4 4 b

shoud return [2 10] or [5 10]???

Edited by author 15.07.2008 06:07

Edited by author 15.07.2008 06:07
Re: I got accepted using O(n^2) algo. Who can do O(n*log(n))?
Послано Alex Tolstov (Vologda STU) 21 мар 2009 19:00
AC in java 0.218sec using O(n^2)
Re: I got accepted using O(n^2) algo. Who can do O(n*log(n))?
Послано Peter Ivanov 6 сен 2009 22:27
You can use some logarithmic tree (stl map structure is OK) for O(n*logn). If you maintain the starting positions of the segments up to date than you can insert a new segment by erasing some segments and eventually divide a segment into two pieces.