Operations on a Matrix

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/OCT19/hindi/SAKTAN.pdf), [Bengali](http://www.codechef.com/download/translated/OCT19/bengali/SAKTAN.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/OCT19/mandarin/SAKTAN.pdf), [Russian](http://www.codechef.com/download/translated/OCT19/russian/SAKTAN.pdf), and [Vietnamese](http://www.codechef.com/download/translated/OCT19/vietnamese/SAKTAN.pdf) as well. "It's totally fun to play troublemakers ― totally."  Lee Pace Sakshi had a matrix with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$). Initially, all cells of this matrix contained $0$s. Let's denote a cell in row $r$ and column $c$ by $(r, c)$. Sakshi is wellknown for troubling others. This time, her friends Nikki and Mansi planned to take revenge and teach her a lesson, so they changed her matrix by performing the following operation $Q$ times:  Choose any valid cell $(x, y)$.  Add $1$ to all the cells in row $x$.  Add $1$ to all the cells in column $y$. For each valid $i$, the cell chosen in the $i$th operation was $(X_i, Y_i)$. Nikki and Mansi challenged Sakshi to find the number of cells in the resulting matrix which contain odd integers. Sakshi is not good at math, since she has spent all her life troubling others, so this time, she really needs your help. Help Sakshi find the answer. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains three spaceseparated integers $N$, $M$ and $Q$.  $Q$ lines follow. For each $i$ ($1 \le i \le Q$), the $i$th of these lines contains two spaceseparated integers $X_i$ and $Y_i$. ### Output For each test case, print a single line containing one integer ― the number of cells with odd values. ### Constraints  $1 \le T \le 300$  $1 \le N, M, Q \le 10^5$  $1 \le X_i \le N$ for each valid $i$  $1 \le Y_i \le M$ for each valid $i$  the sum of $N$ over all test cases does not exceed $3 \cdot 10^5$  the sum of $M$ over all test cases does not exceed $3 \cdot 10^5$  the sum of $Q$ over all test cases does not exceed $3 \cdot 10^5$ ### Subtasks **Subtask #1 (40 points):**  $1 \le N, M, Q \le 300$ **Subtask #2 (40 points):**  $1 \le T \le 3$  $1 \le N \cdot M \le 10^6$  $1 \le Q \le 10^5$ **Subtask #3 (20 points):** original constraints ### Example Input ``` 1 2 2 3 1 1 1 2 2 1 ``` ### Example Output ``` 2 ``` ### Explanation **Example case 1:** After applying the first operation, the matrix becomes: ``` 2 1 1 0 ``` After applying the second operation, it becomes: ``` 3 3 1 1 ``` Finally, after applying the third operation, it becomes: ``` 4 3 3 2 ```Author:  iamabjain 
Editorial  https://discuss.codechef.com/problems/SAKTAN 
Tags  iamabjain, oct19, r_64, simple, simplemath 
Date Added:  19092019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions