Обсуждение @ 1147. Цветная бумага @ Timus Online Judge

Ilya Grebnov[Ivanovo SPU] I know right n*n*logn solution. But how solve this problem faster? [4] // Задача 1147. Цветная бумага 22 ноя 2005 01:55

Ilya Grebnov[Ivanovo SPU] Re: I know right n*n*logn solution. But how solve this problem faster? [2] // Задача 1147. Цветная бумага 22 ноя 2005 01:58

I tried Quadro and RD Trees and others complicated structures, but failed

svr Re: I know right n*n*logn solution. But how solve this problem faster? [1] // Задача 1147. Цветная бумага 1 янв 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?

Denis Koshman Re: I know right n*n*logn solution. But how solve this problem faster? // Задача 1147. Цветная бумага 12 авг 2008 23:37

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

Yuanming YU, Frank Re: I know right n*n*logn solution. But how solve this problem faster? // Задача 1147. Цветная бумага 23 дек 2005 11:40

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.

Обсуждение задачи 1147. Цветная бумага