e-olymp 685. Сумма на параллелепипеде

Задача

Задана трехмерная таблица чисел [latex]a_{ijt}[/latex], где [latex]1\leq i\leq n[/latex], [latex]1\leq j\leq m[/latex], [latex]1\leq t\leq k[/latex]. Для заданных [latex]l_{x}, l_{y}, l_{z},r_{x}, r_{y}, r_{z}[/latex] найдите

[latex]S_{l_{x}, l_{y}, l_{z},r_{x}, r_{y}, r_{z}}=\sum\limits_{i=lx,j=ly,t=lz}^{i\leq rx,j\leq ry,t\leq rz}a_{ijt}[/latex]

Входные данные

В первой строке записаны размеры таблицы — [latex]n, m, k \left ( 1\leq n, m, k\leq 100 \right )[/latex]. Далее записано [latex]n[/latex] блоков по [latex]m[/latex] строк, в каждой из которых записaно по [latex]k[/latex] чисел [latex]a_{ijt} \left ( 1\leq a_{ijt} \leq 1000 \right )[/latex]. Блоки разделены пустой строкой. В очередной строке записано число [latex]q \left ( 1\leq q\leq 10^{6} \right )[/latex] — количество запросов. В следующих [latex]q[/latex] строках описаны запросы [latex]l_{x_{i}}, l_{y_{i}}, l_{z_{i}}, r_{x_{i}}, r_{y_{i}}, r_{z_{i}}[/latex][latex]\left ( 1 \leq l_{x_{i}} \leq r_{x_{i}} \leq n, 1 \leq l_{y_{i}} \leq r_{y_{i}} \leq m, 1 \leq l_{z_{i}} \leq r_{z_{i}} \leq k \right )[/latex] .

Выходные данные

Выведите [latex]q[/latex] чисел в отдельных строках — ответы на запросы.

Тесты

Входные данные Выходные данные
1 2 3 5
1 2 3 4 5
5 4 3 2 1
2 3 1 5 41 2 3 4 5
5 4 3 2 1
2 3 1 5 4
5
1 1 1 1 2 2
1 1 1 2 2 2
1 2 3 2 3 4
1 3 4 2 3 5
1 2 4 2 2 5
12
24
22
18
6

Код

Решение

Создаем массивы arr — массив элементов исходной матрицы, и amountArray — массив количества элементов «на префиксе». В первой тройке вложенных циклов for заполняем массив arr. Затем в трех парах вложенных массивов заполняем соответственно первый «этаж» матрицы amountArray, первую строку и первый столбец всех «этажей». Далее, в тройке вложенных циклов for заполняем оставшиеся элементы массива. После, читаем запросы и выводим ответы.

Ссылки

Related Images:

6 thoughts on “e-olymp 685. Сумма на параллелепипеде

  1. Никита, мне кажется объяснения кода тут излишнее, куда важнее описать формулу запроса, заполнения, и немного объяснить, что означает «на префиксе»

  2. Также тут излишними будут и массив arr ибо можем считывать сразу при заполнении, а также тут не нужна тройка циклов заполняющее начальными данными, учитываю что 0-вые уровни заполнены нулями то формула заполнения также сработает и без начальных данных, только начинать надо не с 2 а с 1

  3. Никита,$\leqslant$-\leqslant и \displaystyle перед суммой не только сделают формулы красивее, но и, возможно, избавят Вас от еще одного комментария.

Добавить комментарий