Блог пользователя SPyofgame

Автор SPyofgame, история, 4 года назад, По-английски

There is an empty rectangle of size

$$$n \times m$$$

where

$$$1 \leq n, m \leq 10^6$$$

We cover the rectangles k times from (u1, v1) to (u2, v2), where

$$$1 \leq k \leq 400$$$
$$$1 \leq u1 \leq u2 \leq n$$$
$$$1 \leq v1 \leq v2 \leq m$$$

The question is: How many squares of that rectangle have been covered ?

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I accidentally read the title of this blog as can someone hit me with this problem