Ctrl K

Покраска строк и столбцов

Средняя
Есть квадратная таблица size × size, изначально заполненная нулями. Дан список покрасок paints, каждая — тройка [kind, index, value]: - если kind == 0, все клетки строки index получают значение value; - если kind == 1, все клетки столбца index получают значение value. Покраски применяются по порядку, новая перезаписывает старую. Верните сумму всех чисел в таблице после последней покраски. Таблица может быть огромной — не стройте её.
Пример 1
size=2, paints=[[0, 0, 5], [1, 1, 2]] → 9

Сначала верхняя строка становится [5, 5], потом правый столбец перекрашивается в 2: таблица [[5, 2], [0, 2]], сумма 9.

Пример 2
size=3, paints=[[1, 0, 4], [1, 0, 1], [0, 2, 3]] → 11

Левый столбец сначала 4, потом 1. Затем нижняя строка — 3 (в том числе её левая клетка). Сумма: 1 + 1 + 3 + 3 + 3 = 11.

Ограничения
  • 1 ≤ size ≤ 10⁴
  • 1 ≤ len(paints) ≤ 5·10⁴
  • kind равен 0 или 1
  • 0 ≤ index < size
  • 0 ≤ value ≤ 10⁵
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСудоку без конфликтов СредняяРазложить анаграммы по группам СредняяНулевые кресты СредняяДерево по прямому и симметричному обходам СредняяДерево по симметричному и обратному обходам Средняя
загружаем Python…
Вход
size=2, paints=[[0, 0, 5], [1, 1, 2]]
Ожидается
9

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