#P17684. [Jboi2026]Christmas Tree

[Jboi2026]Christmas Tree

题目描述

给定一个 N×MN\times M 的整数矩阵 TT,其中 T[i][j]T[i][j] 表示第 ii 行、第 jj 列灯泡的亮度。

定义一棵高度为 HH(H>1H>1)的圣诞树。

选择格子 (i,j)(i,j) 作为树顶的星星。圣诞树包含连续的 HH 行:

i,i+1,…,i+H−1.i,i+1,\ldots,i+H-1.

在第 i+di+d 行(0≤d<H0\le d<H),圣诞树包含列

j−d,j−d+1,…,j+dj-d,j-d+1,\ldots,j+d

上的所有格子。

因此各层宽度依次为

1,3,5,…,2H−1.1,3,5,\ldots,2H-1.

整棵圣诞树必须完全位于矩阵内部。

对于 d=0,1,…,H−1d=0,1,\ldots,H-1,定义第 dd 层的亮度集合:

$$S_d= \left\{ T[i+d][j-d], T[i+d][j-d+1], \ldots, T[i+d][j+d] \right\}.$$

对于每两个相邻层,要求上层的每一个亮度都严格小于下层的每一个亮度。也就是说,对每个 d=0,1,…,H−2d=0,1,\ldots,H-2:

$$\forall x\in S_d,\ \forall y\in S_{d+1},\quad x<y.$$

对于每个高度

k=2,3,…,N,k=2,3,\ldots,N,

求所有恰好高度为 kk 的合法圣诞树中,星星格子 T[i][j]T[i][j] 的最大可能值。

若不存在高度为 kk 的合法圣诞树,输出 -1。

输入格式

第一行:

N M

接下来 NN 行,每行包含 MM 个整数,描述矩阵 TT。

输出格式

输出 N−1N-1 行。

对于 k=2,3,…,Nk=2,3,\ldots,N,依次输出:

  • 高度恰好为 kk 的合法圣诞树中最大的星星亮度;
  • 若不存在,输出 -1。

数据范围

  • 2≤N≤25002\le N\le2500
  • 1≤M≤25001\le M\le2500
  • 1≤T[i][j]≤1091\le T[i][j]\le10^9

子任务

子任务 分值 限制
1 3 M<3M<3
2 5 N=3N=3
3 12 N,M≤50N,M\le50
4 15 N,M≤200N,M\le200
5 19 N,M≤600N,M\le600
6 38 N,M≤900N,M\le900
7 8 无额外限制

样例

输入
4 5
5 1 4 2 7
8 9 10 11 12
18 14 20 16 17
1 1 1 1 1

输出
11
4
-1

对于高度 22,最大的星星亮度为 1111。它下一层的三个亮度为 20,16,1720,16,17,均严格大于 1111。

对于高度 33,最大的合法星星亮度为 44。

不存在高度 44 的合法圣诞树。