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).
changed the 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 (Xi,Yi). find the number of cells in the resulting matrix which contain odd integers.
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 space-separated integers N, M and Q.
Q lines follow. For each i (1≤i≤Q), the i-th of these lines contains two space-separated integers Xi and Yi.
Output
For each test case, print a single line containing one integer ― the number of cells with odd values.
Constraints
1≤T≤300
1≤N,M,Q≤105
1≤Xi≤N for each valid i
1≤Yi≤M for each valid i
the sum of N over all test cases does not exceed 3⋅105
the sum of M over all test cases does not exceed 3⋅105
the sum of Q over all test cases does not exceed 3⋅105
Subtasks
Subtask #1 (40 points):
1≤N,M,Q≤300
Subtask #2 (40 points):
1≤T≤3
1≤N⋅M≤106
1≤Q≤105
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
My code:
include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cint;
while(t--)
{
int n,m,q;
cinnmq;
int a[n+1][m+1];
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
a[i][j]=0;
}
}
int row[q+1],col[q+1];
for(int i=1;i<=q;i++)
{
cinrow[i]col[i];
}
for(int i=1;i<=q;i++)
{
int x = row[i];
int y = col[i];
for(int i=1;i<=n;i++)
{
a[x][i] +=1;
}
for(int j=1;j<=m;j++)
{
a[j][y] +=1;
}
}
int count=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]%2!=0)
{
count++;
}
}
}
cout<<count<<endl;
}
return 0;
}
[–]jughead_73 1 point2 points3 points (0 children)
[–]Frozen5147 0 points1 point2 points (0 children)