Яблоневый сад в клетку


Отправить решение Решать в редакторе

Сложность: 25%
Очки: 100 (частичный балл)
Ограничение по времени: 1.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Яблоневый сад в клетку

Сад Бакыта — таблица n × m, в клетке (i,j) растёт aᵢⱼ яблок. Ответьте на q вопросов: сколько яблок в прямоугольнике с углами (r₁,c₁) и (r₂,c₂).

Формат ввода

В первой строке n, m и q (1 ≤ n · m ≤ 2 · 10⁵, 1 ≤ q ≤ 2 · 10⁵). Далее n строк по m чисел aᵢⱼ (|aᵢⱼ| ≤ 10⁴). Далее q строк: r₁, c₁, r₂, c₂ (1 ≤ r₁ ≤ r₂ ≤ n, 1 ≤ c₁ ≤ c₂ ≤ m).

Формат вывода

Для каждого вопроса — сумму на отдельной строке.

Пример 1

Вход:

2 3 2
1 2 3
4 5 6
1 1 2 2
2 2 2 3

Выход:

12
11

Комментарии

Еще нет ни одного комментария.