Editorial for IOI '18 P2 - Seats - DMOJ: Modern 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)$ ~\mathcal O(HW)~ time and deal with each query in $\mathcal O(H^2 W^2)$ ~\mathcal 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$

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 = HW-1~ inductively in $\mathcal O(HW)$ ~\mathcal O(HW)~ time.

Subtask 3

If $(\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$ .

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

This condition is determinable independently in $\mathcal O(\log(HW))$ ~\mathcal O(\log(HW))~ time using a segment tree. Then each query is dealt with in $\mathcal O((H+W) \log(HW))$ ~\mathcal O((H+W) \log(HW))~ 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)$ ~\mathcal 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, HW-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))$ ~\mathcal O(\log(HW))~ time.

Comments

There are no comments at the moment.