Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Чат
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Земельный комитет

(Время: 3 сек. Память: 16 Мб Сложность: 41%)

Земельный комитет города принял решение о сдаче в аренду части муниципальной территории, имеющей форму прямоугольника размером H на W километров. Стоимость аренды каждого квадратного участка 1×1 км была определена с учётом локальных условий, и занесена в таблицу.

С целью организации открытого тендера на аренду, земельный комитет решил выставить на своём веб-сайте карту территории, и предоставить посетителям возможность узнавать суммарную стоимость аренды для произвольной прямоугольной группы соседних участков.

Данное предложение вызвало большой интерес у населения и предпринимателей, и нагрузка на сервер очень высока.

Требуется написать программу, позволяющую как можно более эффективно рассчитывать стоимость аренды для N запросов. В каждом запросе требуется определить общую стоимость участков внутри прямоугольной группы с противоположными углами, расположенными в элементах таблицы (ai, bi) и (ci, di).

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

В первой строке входного файла INPUT.TXT находятся числа H, W, N (1 ≤ H, W ≤ 100, 1 ≤ N ≤ 1000000). В следующих H строках содержится по W чисел (стоимости участков находятся в диапазоне от 0 до 10000). Далее идут N строк с числами ai bi ci di (1 ≤ ai ≤ ci ≤ H, 1 ≤ bi ≤ di ≤ W).

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

В выходной файл OUTPUT.TXT должен содержать N чисел, по одному числу в строке.

Примеры

INPUT.TXTOUTPUT.TXT
12 3 1
5 1 2
6 7 3
2 1 2 3
16

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483