Задача №114691. Плитка для ванной
У Кости очень много дел — ремонт в самом разгаре! Надо клеить обои, собирать мебель и постоянно вывозить мусор.
Сегодня Костя хочет купить плитку для ванной. Он пришел в магазин и оказался перед большим квадратным стендом с плиткой. Стенд представляет из себя квадрат из \(n \times n\) клеток, каждая клетка которого — маленький кусочек плитки цвета \(c_{i,\,j}\). Магазин продает кусочки плитки пакетами — а именно, купить можно только подквадрат исходного квадрата.
Подквадратом называется любой квадратный фрагмент стенда, то есть любое множество \(S(i_0, j_0, k) = \{c_{i,\,j}\ |\ i_0 \le i < i_0 + k, j_0 \le j < j_0 + k\}\) при \(1 \le i_0, j_0 \le n - k + 1\).
Костя еще не знает, сколько кусочков плитки он хочет купить, и, соответственно, рассматривает подквадраты всех возможных размеров. При этом он точно не хочет слишком разноцветную плитку в ванной, что позволяет ему сузить выбор. Помогите Косте для каждого \(k \le n\) определить количество различных подквадратов размера \(k \times k\), в которых не более \(q\) различных цветов плитки. Подквадраты считаются различными, если их расположение на стенде не совпадает.
В первой строке вводятся два целых положительных числа \(n\), \(q\) (\(1 \le n \le 1500\), \(1 \le q \le 10\)) — размер стенда с плитками и ограничение на количество различных цветов в пакете.
В следующих \(n\) строках вводятся по \(n\) целых положительных чисел \(c_{i,\,j}\) (\(1 \le c_{i,\,j} \le n^2\)) — \(j\)-е число в \(i\)-й строке соответствует цвету плитки в клетке \((i,\,j)\).
Для каждого \(k\) от 1 до \(n\) выведите в отдельной строке по одному целому числу — количество подквадратов размера \(k \times k\), которые интересны Косте.
В первом примере все цвета квадратиков плитки различные. Поскольку Костя не хочет, чтобы в купленном квадрате было больше 4 цветов, он может купить себе любой подквадрат размера \(1 \times 1\) или \(2 \times 2\), но при этом не сможет купить квадрат размера \(3 \times 3\).
Во втором примере есть повторяющиеся цвета. А именно, за счет ограничения \(q = 8\) Костя может купить любой подквадрат \(1 \times 1\) и \(2 \times 2\), а также любой подквадрат \(3 \times 3\), ведь в каждом таком подквадрате всего 7 цветов. Весь стенд размера \(4 \times 4\) Костя купить не сможет, потому что там будет 9 цветов.
Тесты к этой задаче состоят из восьми групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов всех необходимых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Дополнительные ограничения | ||||
| Группа | Баллы | \(n\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 5 | \(n \le 10\) | 0 | |
| 2 | 6 | \(n \le 50\) | 0–1 | |
| 3 | 7 | \(n \le 200\) | 0–2 | |
| 4 | 13 | \(n \le 500\) | 0–3 | |
| 5 | 14 | – | 0 | Количество плиток каждого цвета не превышает 10. |
| 6 | 15 | – | 0 | \(c_{i,\,j} \le 20\) |
| 7 | 16 | – | – | \(q = 1\) |
| 8 | 24 | – | 0–7 | Offline-проверка. |
3 4 1 2 3 4 5 6 7 8 9
9 4 0
4 8 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7
16 9 4 0