HackerEarth Counting In Byteland problem solution

In this HackerEarth Counting In Byteland problem solution For once, let’s assume Byteland to be a 3-dimensional space of size N X N X N. The Lolympics Committee has decided that every contingent representing a country will stay in a hotel at a particular coordinate denoted by its x-axis, y-axis, and z-axis. Now, the Players Welfare Association(PWA) has to answer some queries as well as give accommodation to the Lolympic players. There will be Q number of queries which can be of two types:-

1 x y z val – A contingent consisting of val number of players have been alloted a hotel in the coordinate (x,y,z).
2 x y z X Y Z- Calculate the total number of players who are not residing in the coordinates ranging from (x <= xi <= X, y <= yi <= Y, z <= zi <= Z)

HackerEarth Counting In Byteland problem solution.

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mk make_pair
ll power(ll a, ll b) {
ll x = 1, y = a;
    while(b > 0) {
        if(b%2 == 1) {
            x=(x*y);
            if(x>mod) x%=mod;
        }
        y = (y*y);
        if(y>mod) y%=mod;
        b /= 2;
    }
    return x;
}
ll tree[102][102][102];
int n;
void update(int x, int y, int z, ll val) 
{
    int i,j,k;
    for(i = x; i <= n; i += i&-i) {
        for(j = y; j <= n; j += j&-j) {
            for(k = z; k <= n; k += k&-k) {
                tree[i][j][k] += val;
            }
        }
    }
}

ll read(int x, int y, int z) 
{
    ll sum = 0;
    int i,j,k;
    for(i = x; i > 0; i -= i&-i) {
        for(j = y; j > 0; j -= j&-j) {
            for(k = z; k > 0; k -= k&-k) {
                sum += tree[i][j][k];
            }
        }
    }
    return sum;
}
ll get(int x, int y, int z, int X, int Y, int Z)
{
    return read(X,Y,Z)-read(x,Y,Z)-read(X,y,Z)-read(X,Y,z)+read(x,y,Z)+read(x,Y,z)+read(X,y,z)-read(x,y,z);
}
int main() 
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int q,type,x,y,z,val,X,Y,Z;
    cin>>n>>q;
    n+=1;
    ll total = 0;
    while(q--) {
        cin>>type;
        if(type == 1) {
            cin>>x>>y>>z>>val;
            total += val;
            update(x+1,y+1,z+1,val);
        }
        else {
            cin>>x>>y>>z>>X>>Y>>Z;
            cout<<total-get(x,y,z,X+1,Y+1,Z+1)<<"n";
        }
    }
    return 0;
}

HackerEarth Counting In Byteland problem solution.

Leave a Reply