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, EnochPoon and nathanl3

During the last DMOPC, d did great and scored 4^{th} 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^{th} game, the player sitting at the u_i^{th} row and the v_i^{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?


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 \leq 10

Subtask 2 [20%]

R,C \leq 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^{th} row and the v^{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



  • 1
    kobortor  commented on Nov. 17, 2016, 6:06 p.m. edited

    There was a slight error in the problem statement. The answer / output is the the side length of the square, not the area of the square.

    The error has been corrected.