There is an empty rectangle of size
where
We cover the rectangles k times from (u1, v1) to (u2, v2), where
The question is: How many squares of that rectangle have been covered ?
There is an empty rectangle of size
where
We cover the rectangles k times from (u1, v1) to (u2, v2), where
The question is: How many squares of that rectangle have been covered ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
Don't try to find the state of the rectangle at the end, but rather count how many more squares have been covered after every operation considering all previous operations.
The 400 implies that it is a $$$O(n^3)$$$ solution, we should do something whith each one of the rects $$$n^2$$$ times.
How to find the contribution for the third rect?
Let $$$cells(r_i)$$$ be number of cells in ith rect. Then contribution of first rect equals $$$cells(r_1)$$$. Second is $$$cells(r_2)-cells(intersection(r_1, r_2))$$$
Then it gets interesting. Third is $$$cells(r_3) - cells(intersection(r_3, r_1)) - cells(intersection(r_2, r_1)) + cells(intersection(r_3, r_2))$$$
So, it turns out adding a next rect is adding an intersection of the new rect and all previusly existing rects (and the intersections of them).
Be careful to give every rect a proper sign to know if the number of intersection cells must be added or subtracted.
Can this approach be called Disjoin Set Union ?
I accidentally read the title of this blog as can someone hit me with this problem