Обсуждение @ 1019. Перекрашивание прямой @ Timus Online Judge

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.

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