#3177. 「IOI2019」矩形区域

内存限制:1024 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

19 世纪初,统治者下令在俯瞰美丽河景的高原上建造一座宫殿。这块高原被看做是一个由正方形单元格组成的 n \times m 网格。网格的行从 0 n-1 编号,列从 0 m-1 编号。第 i 行第 j 列( 0 \le i \le n - 1, 0 \le j \le m - 1 )的单元格记为单元格 (i, j) 。每个单元格 (i, j) 有特定的海拔高度,记为 a[i][j]

统治者指示他的建筑师选择一个矩形区域来建造宫殿。该区域不能包含网格边界(第 0 行,第 n-1 行,第 0 列,以及第 m-1 列)上的任何单元格。为此,建筑师应选出四个整数 r_1 r_2 c_1 c_2 1 \le r_1 \le r_2 \le n - 2 1 \le c_1 \le c_2 \le m - 2 ,对应于包括所有满足 r_1 \le i \le r_2 c_1 \le j \le c_2 的单元格 (i, j) 的矩形区域。

此外,一个区域被认为是合法的,当且仅当对于该区域中的每个单元格 (i, j) ,以下条件成立:对于与该区域相邻的、位于第 i 行的两个单元格(单元格 (i, c_1-1) (c_2+1) ),以及与该区域相邻的、位于第 j 列的两个单元格(单元格 (r_1-1, j) (r_2+1, j) ),单元格 (i, j) 的海拔高度必须严格小于这四个单元格的海拔高度。

你的任务是帮助建筑师统计可建宫殿的合法区域的数量(也就是所对应区域为合法的 r_1, r_2, c_1 c_2 的数量)。

输入格式

第一行,两个整数 n m ,表示网格的长和宽。
i+2 行( 0 \le i \le n-1 ): m 个整数,为 a[i][0], a[i][1], \cdots, a[i][m - 1]

输出格式

一行,一个整数,表示合法区域的数量。

样例

样例输入

6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6

样例输出

6

样例解释

一共有 6 个合法区域,分别为:

  • r_1=r_2=1, c_1=c_2=1
  • r_1=1, r_2=2, c_1=c_2=1
  • r_1=r_2=1, c_1=c_2=3
  • r_1=r_2=4, c_1=2,c_2=3
  • r_1=r_2=4, c_1=c_2=3
  • r_1=3,r_2=4,c_1=c_2=3

例如, r_1=1, r_2=2, c_1=c_2=1 对应一个合法区域,原因是以下两个条件都成立:

  • a[1][1]=4 严格小于 a[0][1]=8 a[3][1]=14 a[1][0]=7 ,和 a[1][2]=10
  • a[2][1]=7 严格小于 a[0][1]=8 a[3][1]=14 a[2][0]=9 ,和 a[2][2]=20

数据范围与提示

对于所有数据:

  • 1 \le n, m \le 2500
  • 0 \le a[i][j] \le 7\ 000\ 000 0 \le i \le n - 1, 0 \le j \le m - 1

详细子任务附加限制与分值如下表:

子任务编号 附加限制 分值
1 n, m \le 30 8
2 n, m \le 80 7
3 n, m \le 200 12
4 n, m \le 700 22
5 n \le 3 10
6 0 \le a[i][j] \le 1 13
7 没有任何附加限制 28