DMOPC '18 Contest 2 P6 - Standing Ovation

View as PDF

Submit solution



Points: 30 (partial)
Time limit: 15.0s
Memory limit: 1G
Author:

Problem type

At the Nova Theatre, the balcony seats can be seen as a grid with M rows and N columns. The theatre is packed and the seats are all filled. At the end of the play, K people in the balcony stand to give their applause. The i^{\text{th}} of these K people is sitting in row r_i, column c_i. The rest of the M\times N people will only stand if at least two people adjacent to them are standing. How many people will end up standing?

Constraints

K\le M\times N
1\le r_i\le M for all 1\le i\le K
1\le c_i\le N for all 1\le i\le K

Subtask 1 [10%]

M=2
1\le N\le 100\ 000
1\le K\le 100\ 000

Subtask 2 [30%]

1\le M, N\le 1\ 000
1\le K\le 100\ 000

Subtask 3 [10%]

1\le M, N\le 100\ 000
1\le K\le 1\ 000

Subtask 4 [50%]

1\le M, N\le 100\ 000
1\le K\le 100\ 000

Input Specification

The first line will contain three space-separated integers, M, N, K.
The next K lines each contain two space-separated integers, r_i and c_i, representing the i^{\text{th}} person initially standing.

Sample Input 1

3 4 5
1 1
1 2
1 3
2 1
3 1

Sample Output 1

9

Explanation for Sample 1

Initially, the grid appears as:

S S S O
S O O O
S O O O

where S denotes someone standing and O denotes someone sitting.
Then it becomes:

S S S O
S S O O
S O O O

Then:

S S S O
S S S O
S S O O

Finally:

S S S O
S S S O
S S S O

No more people stand, so the 9 people end up standing.

Sample Input 2

3 5 4
1 1
3 1
1 4
2 5

Sample Output 2

7

Sample Input 3

3 5 4
1 1
3 1
1 3
2 4

Sample Output 3

12

Comments

There are no comments at the moment.