Editorial for IOI '18 P2 - Seats
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 time and deal with each query in time.
Subtask 2
Let the square where the number is written be . The sufficient and necessary condition of forming a rectangle is:
Here, moves between and .
Check if these conditions hold from to inductively in time.
Subtask 3
If , the next satisfying the condition is not less than .
So it is enough to determine this condition in numbers.
This condition is determinable independently in time using a segment tree. Then each query is dealt with in time.
Subtask 4
Memorize and of and for each and recalculate them for between the two swapped numbers for each query.
Subtask 5
Take arbitrarily and color the squares with numbers black and the squares with numbers 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 and count the number of s satisfying the condition efficiently using a lazy propagation segment tree and deal with each query in time.
Subtask 6
Like above, take arbitrarily and color the squares with numbers black and the squares with numbers 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 and count the number of s satisfying the condition efficiently using a lazy propagation segment tree and deal with each query in time.
Comments