Ctrl K

Штампы в углу таблицы

Лёгкая
Есть таблица rows × cols, заполненная нулями. Её по очереди штампуют: штамп stamps[k] = [a, b] прибавляет единицу ко всем клеткам (x, y) с 0 ≤ x < a и 0 ≤ y < b — то есть к прямоугольнику a × b, прижатому к левому верхнему углу. После всех штампов найдите наибольшее число в таблице и верните, в скольких клетках оно стоит. Таблица может быть огромной — строить её не обязательно.
Пример 1
rows=4, cols=5, stamps=[[3, 4], [2, 5]] → 8

Оба штампа покрывают только прямоугольник 2 × 4 в углу: там стоит 2, везде остальное меньше. Таких клеток 8.

Пример 2
rows=2, cols=3, stamps=[] → 6

Штампов не было, все 6 клеток равны нулю — и все они максимальны.

Ограничения
  • 1 ≤ rows, cols ≤ 4 · 10⁴
  • 0 ≤ len(stamps) ≤ 10⁴
  • len(stamps[k]) == 2
  • 1 ≤ a ≤ rows
  • 1 ≤ b ≤ cols
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиПрибавить единицу к числу из цифр ЛёгкаяПотерянный билет ЛёгкаяЛучшее произведение трёх ЛёгкаяСамый большой треугольник на доске ЛёгкаяТени башен из кубиков Лёгкая
загружаем Python…
Вход
rows=4, cols=5, stamps=[[3, 4], [2, 5]]
Ожидается
8

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 113 тестов на сервере, включая скрытые.