Codechef Operations in a matrix

/*

Sakshi had a matrix with N$N$ rows (numbered 1$1$ through N$N$) and M$M$ columns (numbered 1$1$ through M$M$). Initially, all cells of this matrix contained 0$0$-s. Let's denote a cell in row r$r$ and column c$c$ by (r,c)$(r,c)$.

Sakshi is well-known 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$Q$ times:

• Choose any valid cell (x,y)$(x,y)$.
• Add 1$1$ to all the cells in row x$x$.
• Add 1$1$ to all the cells in column y$y$.

For each valid i$i$, the cell chosen in the i$i$-th operation was (Xi,Yi)$(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$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains three space-separated integers N$N$, M$M$ and Q$Q$.
• Q$Q$ lines follow. For each i$i$ (1≤i≤Q$1\le i\le Q$), the i$i$-th of these lines contains two space-separated integers Xi$X_i$ and Yi$Y_i$.

Output

For each test case, print a single line containing one integer ― the number of cells with odd values.

Constraints

• 1≤T≤300$1\le T\le 300$
• 1≤N,M,Q≤105$1\le N,M,Q\le {10}^5$
• 1≤Xi≤N$1\le X_i\le N$ for each valid i$i$
• 1≤Yi≤M$1\le Y_i\le M$ for each valid i$i$
• the sum of N$N$ over all test cases does not exceed 3⋅105$3\cdot {10}^5$
• the sum of M$M$ over all test cases does not exceed 3⋅105$3\cdot {10}^5$
• the sum of Q$Q$ over all test cases does not exceed 3⋅105$3\cdot {10}^5$

Subtasks

Subtask #1 (40 points):

• 1≤N,M,Q≤300$1\le N,M,Q\le 300$

Subtask #2 (40 points):

• 1≤T≤3$1\le T\le 3$
• 1≤N⋅M≤106$1\le N\cdot M\le {10}^6$
• 1≤Q≤105$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

*/

---- Method 1:-  My second logic -- first was using a matrix (naive approach)which gave Seg Fault as inputs are very large, so here I have implemented using an array took 3 hours but this also gave seg fault as inputs are very very large .. so, just know the logic as its very precious and it works for generic inputs 

I have also written Method 2 which is after the contest which got 100 marks so, see the difference in both  codes

// method 1 using arrays


#include<bits/stdc++.h>
using namespace std;
int i,j;

int main()
{
    int t,x,y;
    cin>>t;
    while(t--)
    {int n,m,q;
        cin>>n>>m>>q;
        int a[n*m]={0};
        int k;
        for(k=0;k<q;k++)
        {
            cin>>x>>y;
            x=x-1;
            y=y-1;
            // for row
         for(i=n*x; i<n*(x)+n;i++)
         {
             a[i]+=1;
             //cout<<i<<" r"<<" ";
         }
         // for col
         int p=0;
            for( i=y%(m); i<n*m ;i=((m)*p)+y%(m))
            {
                p++;
               
                a[i]+=1;
                // cout<<i<<" c"<<" ";
            }
                   
        }
       
       
       
       
        int c=0;
        for(i=0;i<n*m;i++)
    {
       
        //cout<<a[i][j]<<" ";
        if(a[i]%2!=0)
        {
            c++;
        }
        //cout<<endl;
      // cout<<a[i]<<" ";
        }
   
    cout<<c<<endl;
    }

}

--- Method -2 gave 100 marks --Logic explained beow---------------------------

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        long long n,m,q;
        cin>>n>>m>>q;

        long long r[n]={0},c[m]={0};

        for(int i=0;i<q;i++)
        {
            long long x,y;
            cin>>x>>y;
            r[x-1]++;
            c[y-1]++;
        }

        long long a1=0,a2=0; //a1 and a2 are row even count  and row odd count respectively
        for(int i=0;i<n;i++)
        {
            if(r[i]%2==0){
                a1++;
            }
            else
            {
                a2++;
            }
        }
       
        long long b1=0,b2=0;
        for(int i=0;i<m;i++)
        {
            if(c[i]%2==0){
                b1++;
            }
            else
            {
                b2++;
            }
        }
        // so we know number of rows which are even  and no of colum which are odd and no of rows which are odd 
        
        // we want number of odd elemts in resultant matrix
        // we can get odd by doing sum of even and odd 
// extra info (not for this problem but genric) if we want even elements then there would  be 2 ways even +even and odd+odd

// we know that a1 rows are even,  there would be  (no of column elemts in a row, but out of them b2 columns are odd which will yeild odd result)
// similary if we got ( a2) no of rows which are odd , then we will find (b2) no of rows which are even to multiply and values which yeild an odd result

// so simply sum both to get total odds

        cout<<a1*b2+b1*a2<<endl;

   }
}