Editorial for IOI '18 P2 - Seats - Olympiads Online Judge

Editorial for IOI '18 P2 - Seats

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Subtask 1

Determine whether a set of squares forms a rectangle or not in $\mathcal O(HW)$ $O (H W)$ time and deal with each query in $\mathcal O(H^2 W^2)$ $O (H^{2} W^{2})$ time.

Subtask 2

Let the square where the number $i$ $i$ is written be $(r_i, c_i)$ $(r_{i}, c_{i})$ . The sufficient and necessary condition of $(r_0, c_0), \dots, (r_t, c_t)$ $(r_{0}, c_{0}), \dots, (r_{t}, c_{t})$ forming a rectangle is:

$\displaystyle (\max r_i - \min r_i + 1)(\max c_i - \min c_i + 1) = t+1$ $(max r_{i} - min r_{i} + 1) (max c_{i} - min c_{i} + 1) = t + 1$

Here, $i$ $i$ moves between $0$ $0$ and $t$ $t$ .

Check if these conditions hold from $t = 0$ $t = 0$ to $t = HW-1$ $t = H W - 1$ inductively in $\mathcal O(HW)$ $O (H W)$ time.

Subtask 3

If $(\max r_i - \min r_i + 1)(\max c_i - \min c_i + 1) > t+1$ $(max r_{i} - min r_{i} + 1) (max c_{i} - min c_{i} + 1) > t + 1$ , the next $t$ $t$ satisfying the condition is not less than $(\max r_i - \min r_i + 1)(\max c_i - \min c_i + 1)-1$ $(max r_{i} - min r_{i} + 1) (max c_{i} - min c_{i} + 1) - 1$ .

So it is enough to determine this condition in $\mathcal O(H+W)$ $O (H + W)$ numbers.

This condition is determinable independently in $\mathcal O(\log(HW))$ $O (\log (H W))$ time using a segment tree. Then each query is dealt with in $\mathcal O((H+W) \log(HW))$ $O ((H + W) \log (H W))$ time.

Subtask 4

Memorize $\max$ $max$ and $\min$ $min$ of $r_i$ $r_{i}$ and $c_i$ $c_{i}$ for each $t$ $t$ and recalculate them for $t$ $t$ between the two swapped numbers for each query.

Subtask 5

Take $t$ $t$ arbitrarily and color the squares with numbers $0, \dots, t$ $0, \dots, t$ black and the squares with numbers $t+1, \dots, W-1$ $t + 1, \dots, W - 1$ white (and add white squares outside of the rectangle.)

The sufficient and necessary condition of black squares forming a rectangle is that the number of pairs of adjacent two squares with different colors is two.

Manage the numbers of such pairs of squares for all values of $t$ $t$ and count the number of $t$ $t$ s satisfying the condition efficiently using a lazy propagation segment tree and deal with each query in $\mathcal O(\log W)$ $O (\log W)$ time.

Subtask 6

Like above, take $t$ $t$ arbitrarily and color the squares with numbers $0, \dots, t$ $0, \dots, t$ black and the squares with numbers $t+1, \dots, HW-1$ $t + 1, \dots, H W - 1$ white (and add white squares outside of the rectangle.)

Pay attention to two-times-two squares (sets of adjacent four squares.)

The sufficient and necessary condition of black squares forming a rectangle is as follows:

There are only four two-times-two squares which contain exactly one black square.
There are no two-times-two squares which contain exactly three black squares.

Manage the numbers of such two-times-two squares for all values of $t$ $t$ and count the number of $t$ $t$ s satisfying the condition efficiently using a lazy propagation segment tree and deal with each query in $\mathcal O(\log(HW))$ $O (\log (H W))$ time.

Comments

There are no comments at the moment.