Войти Регистрация
Алгоритмы

131. Заказы такси в прямоугольнике карты

Средняя

Карта разбита на клетки 500 × 500 метров, grid[i][j] — заказы Яндекс Такси в клетке за последний час.

Запрос [r1, c1, r2, c2] — прямоугольник от клетки (r1, c1) до (r2, c2) включительно. Верните число заказов для каждого запроса из queries в том же порядке.

В работе: Повышенный коэффициент считают по районам — прямоугольникам из клеток, и пересчитывают каждую минуту.

Пример 1

Ввод
grid = [[3, 0, 1], [5, 2, 4], [1, 1, 7]]
queries = [[0, 0, 1, 1], [1, 1, 2, 2], [0, 0, 2, 2]]
Вывод
[10, 14, 24]

Левый верхний квадрат 2 × 2: 3 + 0 + 5 + 2 = 10.

Пример 2

Ввод
grid = [[8]]
queries = [[0, 0, 0, 0]]
Вывод
[8]

Ограничения

  • 1 ≤ h, w ≤ 500
  • 0 ≤ grid[i][j] ≤ 10³
  • 0 ≤ число запросов ≤ 10⁵
  • r1 ≤ r2, c1 ≤ c2
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def rect_orders(grid, queries):
Префиксные суммы 2DМатрицацельO(n)

Источник: наша задача на данных Яндекса. Условие пересказано своими словами.