TLE '16 Contest 3 P5 - LAN Party

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Java 8 1.8s
Python 1.8s
Memory limit: 256M

Problem types
From left to right: d, ZQFMGB12, jlsajfj, ChaSiu and nathanl3

During the last DMOPC, d did great and scored 4th place! (Only to be beaten by Thornhill of course.) ZQFMGB12 is so happy for d that he decided to throw a LAN party with the entire school. The party is organized into R rows of seats. Each row has C seats. Initially, there is one player in each seat. As the event goes on, a person's laptop battery might run dry, which causes them to pack up and go home.

ZQFMGB12 will host M games. Before each game, a single player's laptop battery runs out and they leave the party. Specifically, before the i^\text{th} game, the player sitting at the u_i^\text{th} row and the v_i^\text{th} column leaves the party. After this person leaves, ZQFMGB12 needs to choose players to play in the upcoming game, so he chooses a square of seats such that all seats in the square are occupied by a player.

Before each game, ZQFMGB12 wants to know the side length of the greatest square of players he can invite for that game. Can you help him?


For all subtasks:

1 \le R, C \le 350

1 \le M \le R \cdot C

1 \le u \le R

1 \le v \le C

Subtask 1 [20%]

R, C \le 10

Subtask 2 [20%]

R, C \le 50

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line will contain R and C, the number of rows and columns respectively.

The second line will contain M, the players that will leave throughout the event.

The next M lines will contain integers u and v, indicating that the person at the u^\text{th} row and the v^\text{th} column leaves because his or her battery dies. It is guaranteed that the player sitting at (u,v) has not already left.

Output Specification

For each of the M lines, output the side length of the largest square of players that ZQFMGB12 can still invite to his game. If there are no players remaining, print 0.

Sample Input

3 3
3 3
3 2
2 2

Sample Output



There are no comments at the moment.