Dull Chocolates
Time limit9sMemory limit512 MB
Count prefix rectangles of a huge grid whose parity of white cells is odd versus even, given at most 1000 white cells.
- Level
Hard8 of 10
- Topics
- Prefix sum, Sorting, Combinatorics, Math
- Solved
- No attempts yet
Problem
Fouad wants to eat a chocolate bar, so he bought a rectangular chocolate bar that has N rows and M columns of chocolate.
Fouad found that most of the cells in that chocolate bar are dark chocolate except for K cells which are white chocolate. Now, he wants to eat a prefix sub-grid of the bar. A prefix sub-grid is a rectangular sub-grid that starts at the first cell (1, 1) and ends at any cell (i, j). Fouad is also wondering how many perfect prefix sub-grids of the bar. A perfect prefix sub-grid is a one that contains an odd number of white chocolate cells.
Help Fouad find the number of perfect prefix sub-grids and non-perfect prefix sub-grids.
Input
The first line of the input containing a single integer T specifying the number of test cases.
Each test case begins with a line containing three integers N, M, and K (1 ≤ N, M ≤ 109, 0 ≤ K ≤ 103), in which N and M are the number of rows and columns in the chocolate bar, respectively, and K is the number of white chocolate cells.
Then K lines follow, each line containing two integers Xi and Yi (1 ≤ Xi ≤ N, 1 ≤ Yi ≤ M), giving the positions of the white chocolate cells. It is guaranteed that all the given positions are unique.
Output
For each test case, print a single line containing two space-separated integers representing the number of perfect prefix sub-grids and non-perfect prefix sub-grids, respectively.
Hint
In the second test case, the chocolate bar can be represented as follows:
ddd
dwd
ddd
in which 'd' represents dark chocolate cells while 'w' represents white chocolate cells. There are four perfect prefix sub-grids that end at cells: (2, 2), (2, 3), (3, 2), and (3, 3).