|
|
back to boardI know right n*n*logn solution. But how solve this problem faster? Re: I know right n*n*logn solution. But how solve this problem faster? I tried Quadro and RD Trees and others complicated structures, but failed Re: I know right n*n*logn solution. But how solve this problem faster? I use O(n*n*logn)to AC, too.
And my algo can improve to O(nlogn).
I make y coordinate as an Interval tree.
In my O(n*n*logn) algo,Insert the interval into the tree when x coordinate is different is independent,so it need n time for searching in different x.
In fact, the x coordinate which is nearby may be dependent,so we don't have to insert some intervals once more.
There are O(n) intervals, each of them just inserts and deletes one time,so it is total up to O(nlogn).
Sorry for my bad English. Re: I know right n*n*logn solution. But how solve this problem faster? Posted by svr 1 Jan 2008 13:44 How it can be?
With such various methods author has TLE,
I got AC 0.9c with O(N*N*lgn) and interval tree
but many authors have 0.001c AC on the same tests? Re: I know right n*n*logn solution. But how solve this problem faster? I scan per-row, tracking topmos rectangle in a heap. X coordinates can be sorted only once (then just skip rectangles outside of the current slice) - this improved time from 0.75 sec to 0.28 sec
Edited by author 12.08.2008 23:37 |
|
|
