Discussion @ 1019. Line Painting @ Timus Online Judge

I got accepted using O(n^2) algo. Who can do O(n*log(n))?

Posted by KRSU 2 4 Mar 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))?

Posted by b4die 19 Jul 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))?

Posted by tyzwsai 27 Jul 2007 08:17

use segment tree

Re: I got accepted using O(n^2) algo. Who can do O(n*log(n))?

Posted by LiuKe 24 Nov 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))?

Posted by Rudolf 15 Jul 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))?

Posted by Alex Tolstov (Vologda STU) 21 Mar 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))?

Posted by Peter Ivanov 6 Sep 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.

Discussion of Problem 1019. Line Painting