TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5962
  • 题目
  • P5962「IOI2019」矩形区域
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 5s,1024m
    问题描述

    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)\)\((r_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$

    点此提交