|
|
вернуться в форум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))? 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))? 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. |
|
|