#C4754. Taco Grid Maximum
Taco Grid Maximum
Taco Grid Maximum
You are given a grid of size \(m \times n\) where each cell is initially 0. You are also provided with a list of operations. Each operation is represented as a pair of positive integers \([a, b]\), and applying an operation increments by 1 all cells in the submatrix defined by the top-left corner \((0,0)\) to \((a-1, b-1)\). After performing all operations, some cells will contain the maximum integer in the grid. Your task is to determine the number of cells that have this maximum value.
Hint: The final maximum value appears in the cells that lie in the intersection of the first \(\min(a)\) rows and the first \(\min(b)\) columns across all operations. Therefore, the answer is \(\min(a) \times \min(b)\). If no operations are performed, every cell in the grid retains the same value (zero), and thus all \(m \times n\) cells are counted.
inputFormat
The input is read from stdin
and has the following format:
m n k a1 b1 a2 b2 ... ak bk
Here, \(m\) and \(n\) are the dimensions of the grid. The integer \(k\) represents the number of operations, followed by \(k\) lines each containing two space-separated integers \(a\) and \(b\).
outputFormat
Output a single integer to stdout
– the number of cells containing the maximum integer after applying all operations.
3 3
2
2 2
3 3
4
</p>