Header Ad

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. 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. 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


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;
}


Post a Comment

0 Comments