BSSPC '21 S4 - Child Prodigy Chadstin

View as PDF

Submit solution


Points: 17 (partial)
Time limit: 5.0s
Memory limit: 256M

Author:
Problem types

Austin the smurfing smurf orzianna main has an N \times M binary matrix he wants to compress.

A single compression consists of splitting the matrix into \frac{NM}{4} adjacent 2 \times 2 non overlapping blocks and constructing a new \frac{N}{2}\times\frac{M}{2} matrix in which each bit is representative of a single block in the original matrix, given that all 4 bits were of the same value. The value of a bit in the new matrix is the same as that of the 4 bits in the block it represents. The adjacency of bits in the new matrix reflects that of the blocks in the original matrix. The entire matrix can only be compressed if each block only contains bits of the same value.

For example, the following matrices are compressible: \displaystyle 
\newcommand\matrix[1]{\begin{bmatrix}#1\end{bmatrix}}
\matrix{
    1\ 1\ 0\ 0\\
    1\ 1\ 0\ 0\\
    0\ 0\ 1\ 1\\
    0\ 0\ 1\ 1\\
}
\rightarrow
\matrix{
    1\ 0\\
    0\ 1\\
}
\qquad
\matrix{
    1\ 1\ 1\ 1\ 1\ 1\\
    1\ 1\ 1\ 1\ 1\ 1\\
    1\ 1\ 0\ 0\ 0\ 0\\
    1\ 1\ 0\ 0\ 0\ 0\\
    1\ 1\ 0\ 0\ 1\ 1\\
    1\ 1\ 0\ 0\ 1\ 1\\
}
\rightarrow
\matrix{
    1\ 1\ 1\\
    1\ 0\ 0\\
    1\ 0\ 1\\
}
\qquad
\matrix{
    1\ 1\ 0\ 0\\
    1\ 1\ 0\ 0\\
}
\rightarrow
\matrix{
    1\ 0\\
}

While these are not: \displaystyle 
\matrix{1\ 1\\0\ 1}
\qquad
\matrix{
    0\ 0\ 0\ 1\ 1\ 1\ 0\ 0\ 0\\
    0\ 0\ 0\ 1\ 1\ 1\ 0\ 0\ 0\\
    0\ 0\ 0\ 1\ 1\ 1\ 0\ 0\ 0\\
    1\ 1\ 1\ 0\ 0\ 0\ 1\ 1\ 1\\
    1\ 1\ 1\ 0\ 0\ 0\ 1\ 1\ 1\\
    1\ 1\ 1\ 0\ 0\ 0\ 1\ 1\ 1\\
    0\ 0\ 0\ 1\ 1\ 1\ 0\ 0\ 0\\
    0\ 0\ 0\ 1\ 1\ 1\ 0\ 0\ 0\\
    0\ 0\ 0\ 1\ 1\ 1\ 0\ 0\ 0\\
}
Finally, some can be compressed multiple times: \displaystyle 
\matrix{
    1\ 1\ 1\ 1\\
    1\ 1\ 1\ 1\\
    1\ 1\ 1\ 1\\
    1\ 1\ 1\ 1\\
}
\rightarrow
\matrix{
    1\ 1\\
    1\ 1\\
}
\rightarrow
\matrix{
    1
}

Austin knows the top left (t_i,l_i) and bottom right (b_i,r_i) row and column numbers of K possibly overlapping rectangles within the matrix. He knows that all bits within these rectangles are of value 1, while all bits that aren't in any of the specified rectangles are of value 0. Given these rectangles, can you help him find out how many times he can compress his matrix?

Constraints

1 \leq N,M \leq 10^9

1 \leq K \leq 2\times10^5

1 \leq t_i \leq b_i \leq N

1 \leq l_i \leq r_i \leq M

Subtask 1 [20%]

1 \leq N,M \leq 5\times10^3

Subtask 2 [10%]

1 \leq K \leq 2500

Subtask 3 [30%]

1 \leq N,M \leq 10^6

Subtask 4 [40%]

No additional constraints.

Input Specification

The first line contains three integers N, M, and K, which represent the number of rows in the matrix, the number of columns in the matrix, and the number of rectangles in the matrix, respectively.

The next K lines each contain four integers t_i, l_i, b_i, and r_i - the row and column numbers of the top left and bottom right corners of the i^\text{th} rectangle.

Output Specification

Output a single integer, the number of times the compression algorithm can be applied to the given matrix.

Sample Input 1

4 4 2
1 1 2 2
3 3 4 4

Sample Output 1

1

Sample Input 2

6 6 4
1 2 2 6
2 1 6 2
1 1 1 1
5 5 6 6

Sample Output 2

1

Sample Input 3

2 4 1
1 1 2 2

Sample Output 3

1

Sample Input 4

2 2 3
1 1 1 1
1 2 1 2
2 2 2 2

Sample Output 4

0

Sample Input 5

9 9 4
4 1 6 3
1 4 3 6
4 7 6 9
7 4 9 6

Sample Output 5

0

Sample Input 6

4 4 2
1 1 3 4
4 1 4 4

Sample Output 6

2

Comments

There are no comments at the moment.