HackerEarth Xor Rectangle problem solution

In this HackerEarth Xor Rectangle problem solution, You have an array of N integers S1, S2, … SN. Consider a N x N matrix such that Aij = Si XOR SJ.

You have been given Q queries. Each query consists of four integers x1, y1, x2, y2 which denotes a submatrix with (x1, y1) as their top-left corner and (x2, y2) as their bottom-right corner such that x1 <= x2 and y1 <= y2. For each query, you have to print the summation of all integers lying in queried submatrix.

HackerEarth Xor Rectangle problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
int s[1000011][32];
int p[1000011];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    for(int i=1;i<=N;i++) {
        cin >> p[i];
        for(int j=0;j<20;j++) {
            if(p[i]&(1<<j)) {
                s[i][j]++;
            }
            s[i][j]+=s[i-1][j];
        }
    }
    ll o1,o2,z1,z2;
    int Q,x1,y1,x2,y2;
    cin >> Q;
    while(Q--) {
        cin >> x1 >> y1 >> x2 >> y2;
        ll ans = 0;
        rep(j,20) {
            o1 = s[x2][j]-s[x1-1][j];
            z1 = x2-x1+1 - o1;
            o2 = s[y2][j]-s[y1-1][j];
            z2 = y2-y1+1 - o2;
            ans+=(o1*z2+o2*z1)*(1LL<<j);
        }
        cout << ans << "n";
    }
}

Second solution

#pragma GCC optimize("O3")
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>

#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk

#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds
#define ends asdgahhfdsfshdshfd

#define eps 1e-11
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 512

#define ldouble long double

using namespace std;

long long INF = 1e9;
const int N = 1200031;

int tests,n;
int ar[N],s[N][22];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;

    for (int i=1;i<=n;i++)
    {
        cin>>ar[i];
        for (int j=0;j<20;j++)
        {
            s[i][j]=s[i-1][j];
            if (ar[i]&(1<<j))
                s[i][j]+=1;
        }
    }

    cin>>tests;
    for (;tests;--tests)
    {
        int a,b,c,d;
        cin>>a>>c>>b>>d;

        long long ans=0;
        for (int bit=0;bit<20;bit++)
        {
            int cnt1=s[b][bit]-s[a-1][bit];
            int cnt2=(b-a+1)-cnt1;
            int cnt3=s[d][bit]-s[c-1][bit];
            int cnt4=(d-c+1)-cnt3;
            ans+=(1ll<<bit)*cnt1*cnt4+(1ll<<bit)*cnt2*cnt3;
        }
        cout<<ans<<"n";
    }

    return 0;
}

coding problems solutions