Cerinta completa

Chinese Version
Russian Version

Define a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinates (1,1,1) and the last block is defined by the coordinates (n,n,n). There are two types of queries.

UPDATE x y z W

Update the value of block (x,y,z) to W.

QUERY x1 y1 z1 x2 y2 z2

Calculate the sum of the values of blocks whose x coordinate is between x1 and x2 (inclusive), y coordinate between y1 and y2 (inclusive) and z coordinate between z1 and z2 (inclusive).

Function Description

Complete the cubeSum function in the editor below.

cubeSum has the following parameters:
– *int n: the dimensions of the 3-d matrix
– string operations[m]: the operations to perform

Returns
– int[]: the results of each QUERY operation

Input Format
The first line contains an integer , the number of test-cases. testcases follow.

For each test case, the first line contains two space-separated integers, and .
defines the matrix.
defines the number of operations.
The next lines will contain an operation either of these forms: 

 1. UPDATE x y z W
 2. QUERY  x1 y1 z1 x2 y2 z2

Constraints







-109 \le W \le 109

Sample Input

2
4 5
UPDATE 2 2 2 4
QUERY 1 1 1 3 3 3
UPDATE 1 1 1 23
QUERY 2 2 2 4 4 4
QUERY 1 1 1 3 3 3
2 4
UPDATE 2 2 2 1
QUERY 1 1 1 1 1 1
QUERY 1 1 1 2 2 2
QUERY 2 2 2 2 2 2

Sample Output

4
4
27
0
1
1

Explanation
In the first test case, there is a cube of 4 * 4 * 4 and there are 5 queries. Initially all the cells (1,1,1) to (4,4,4) are 0.
UPDATE 2 2 2 4 makes the cell (2,2,2) = 4
QUERY 1 1 1 3 3 3. As (2,2,2) is updated to 4 and the rest are all 0. The answer to this query is 4.
UPDATE 1 1 1 23. updates the cell (1,1,1) to 23.
QUERY 2 2 2 4 4 4. Only the cell (1,1,1) and (2,2,2) are non-zero and (1,1,1) is not between (2,2,2) and (4,4,4). So, the answer is 4.
QUERY 1 1 1 3 3 3. 2 cells are non-zero and their sum is 23+4 = 27.

Limbajul de programare folosit: cpp14

Cod:

#include <bits/stdc++.h>
using namespace std;
struct BIT3D {
    int n;
    vector<vector<vector<long long>>> bit;
    BIT3D(int n): n(n), bit(n+1, vector<vector<long long>>(n+1, vector<long long>(n+1, 0))) {}
    void add(int x, int y, int z, long long v) {
        for (int i = x; i <= n; i += i & -i)
            for (int j = y; j <= n; j += j & -j)
                for (int k = z; k <= n; k += k & -k)
                    bit[i][j][k] += v;
    }
    long long sum(int x, int y, int z) const {
        long long s = 0;
        for (int i = x; i > 0; i -= i & -i)
            for (int j = y; j > 0; j -= j & -j)
                for (int k = z; k > 0; k -= k & -k)
                    s += bit[i][j][k];
        return s;
    }
    long long query(int x1, int y1, int z1, int x2, int y2, int z2) const {
        auto S = [&](int x, int y, int z) { return sum(x, y, z); };
        return S(x2,y2,z2)-S(x1-1,y2,z2)-S(x2,y1-1,z2)-S(x2,y2,z1-1)
             + S(x1-1,y1-1,z2)+S(x1-1,y2,z1-1)+S(x2,y1-1,z1-1)-S(x1-1,y1-1,z1-1);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int N, M;
        cin >> N >> M;
        BIT3D bit(N);
        map<tuple<int,int,int>, long long> cur;
        while (M--) {
            string op;
            cin >> op;
            if (op == "UPDATE") {
                int x, y, z; long long w;
                cin >> x >> y >> z >> w;
                auto key = make_tuple(x,y,z);
                long long old = cur.count(key) ? cur[key] : 0;
                cur[key] = w;
                bit.add(x,y,z,w-old);
            } else {
                int x1, y1, z1, x2, y2, z2;
                cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2;
                cout << bit.query(x1,y1,z1,x2,y2,z2) << '\n';
            }
        }
    }
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464654836

Link challenge: https://www.hackerrank.com/challenges/cube-summation/problem

Cube Summation