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

132. Где ловят хотя бы t вышек

Средняя

Район разбит на сетку h × w клеток по 100 метров. Зона покрытия каждой базовой станции МТС упрощена до прямоугольника [r1, c1, r2, c2] — клетки от (r1, c1) до (r2, c2) включительно.

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

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

Пример 1

Ввод
h = 4
w = 5
zones = [[0, 0, 2, 2], [1, 1, 3, 4], [2, 0, 2, 4]]
t = 2
Вывод
7

Две клетки в строке 1 и вся строка 2 — 7 клеток.

Пример 2

Ввод
h = 2
w = 2
zones = []
t = 1
Вывод
0

Вышек нет.

Ограничения

  • 1 ≤ h, w ≤ 500
  • 0 ≤ число зон ≤ 10⁵
  • 1 ≤ t ≤ 10⁵
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def covered_cells(h, w, zones, t):
Разностный массив 2DПрефиксные суммы 2DМатрицацельO(n)

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