|
|
back to boardI 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))? 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))? 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. |
|
|