P2105 K Queens

Xiao Z recently found a chessboard with $n$ rows and $m$ columns. The row and column coordinates of the cells are numbered starting from $1$. He wants to place $K$ queens on the board. He wants to know how many cells will not be attacked after he places these $K$ queens. Note: A queen attacks the entire row, the entire column, and both diagonals that pass through its position.

The first line contains three positive integers $n,m,K$, representing the number of rows and columns of the board, and the number of queens Xiao Z places. The next $K$ lines each contain two positive integers $x,y$, indicating that a queen is placed at row $x$, column $y$. It is guaranteed that no two queens are placed on the same cell.

Output a single integer: the number of cells on the board that are not attacked.

- For $30\%$ of the testdata, $1\le n,m\le 5\times 10^3$, $1\le K\le 500$. - For an additional $10\%$ of the testdata, $K=1$. - For $100\%$ of the testdata, $1\le n,m\le 2\times 10^4$, $1\le K\le 500$. Translated by ChatGPT 5