262 . 美麗的座位
TopCoder
Tags
Description
你即將在一個長方形場館中舉行一場國際程式競賽，場館可容納 $HW$ 個座位，安排成 $H$ 個橫列和 $W$ 個直行。橫列編號為 $1$ 到 $H$，直行編號為 $1$ 到 $W$。在橫列 $r$ 和直行 $c$ 的座位用 $(r,c)$ 標記。你邀請了 $HW$ 位選手，編號為 $1$ 到 $HW$，你也做了一張座位圖，座位圖中每個座位恰好指定一位選手。
場館中的一組座位 $S$ 可被稱作「長方形」，如果存在整數 $r_1,r_2,c_1,c_2$ 滿足以下條件：
- $0\le r_1\le r_2\le H-1$
- $0\le c_1\le c_2\le W-1$
- $S$ 就是滿足 $r_1\le r\le r_2$ 和 $c_1\le c\le c_2$ 的全部座位 $(r,c)$。
我們說一組長方形的 $k$ 個座位 ($1\le k\le HW$) 是「美麗的」，如果座位指定在這組的選手編號是一組連續正整數的排列，即若我們把這 $k$ 個座位上的選手蒐集起來丟進一個序列 $B$，並加以排序的話，那 $B_1 = B_2 - 1, B_2 = B_3 - 1, \ldots, B_{i - 1} = B_i - 1, \ldots, B_{\lvert B\rvert - 1} = B_{\lvert B \rvert} - 1$ 將會成立。座位圖的「美麗程度」則是圖中可找出的美麗長方形座位組的個數。
你的目標是計算座位圖的「美麗程度」。
Input Format
輸入首行兩個正整數 $H,W$，變數意義如題目所敘。
接下來 $H$ 行，每行 $W$ 個數字以單一空格隔開，代表座位圖的內容。
- $1\le H\times W\le 10^ 6$
Output Format
輸出座位圖的「美麗程度」。
Sample Input 1
10 9 11 12
5 1 4 8
2 7 6 3
Sample Output 1
Hints
範測測資一中，形成矩形的連續正整數區間分別如下：
$[1,1],[1,8],[1,12],[2,2],[3,3],[4,4],[5,5],[6,6],[6,7],[7,7],$
$[8,8],[9,9],[9,10],[9,11],[9,12],[10,10],[11,11],[11,12],[12,12]$
Problem Source
IOICamp 2020 Day4 pF
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~41 | 無額外限制 | 100 |