262 . 美麗的座位

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

baluteshih

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Tags

ioicamp ioicamp-2020

Description

你即將在一個長方形場館中舉行一場國際程式競賽，場館可容納 HW 個座位，安排成 H 個橫列和 W 個直行。橫列編號為 1 到 H，直行編號為 1 到 W。在橫列 r 和直行 c 的座位用 (r,c) 標記。你邀請了 HW 位選手，編號為 1 到 HW，你也做了一張座位圖，座位圖中每個座位恰好指定一位選手。

場館中的一組座位 S 可被稱作「長方形」，如果存在整數 r1,r2,c1,c2 滿足以下條件：

  • 0≤r1≤r2≤H−1
  • 0≤c1≤c2≤W−1
  • S 就是滿足 r1≤r≤r2 和 c1≤c≤c2 的全部座位 (r,c)。

我們說一組長方形的 k 個座位 (1≤k≤HW) 是「美麗的」，如果座位指定在這組的選手編號是一組連續正整數的排列，即若我們把這 k 個座位上的選手蒐集起來丟進一個序列 B，並加以排序的話，那 B1=B2−1,B2=B3−1,…,Bi−1=Bi−1,…,B|B|−1=B|B|−1 將會成立。座位圖的「美麗程度」則是圖中可找出的美麗長方形座位組的個數。

你的目標是計算座位圖的「美麗程度」。

Input Format

輸入首行兩個正整數 H,W，變數意義如題目所敘。

接下來 H 行，每行 W 個數字以單一空格隔開，代表座位圖的內容。

  • 1≤H×W≤106

Output Format

輸出座位圖的「美麗程度」。

Sample Input 1

3 4
10 9 11 12
5 1 4 8
2 7 6 3

Sample Output 1

19

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3500 524288 65536 1 2
1 3500 524288 65536 2
2 3500 524288 65536 2
3 3500 524288 65536 2
4 3500 524288 65536 2
5 3500 524288 65536 2
6 3500 524288 65536 2
7 3500 524288 65536 2
8 3500 524288 65536 2
9 3500 524288 65536 2
10 3500 524288 65536 2
11 3500 524288 65536 2
12 3500 524288 65536 2
13 3500 524288 65536 2
14 3500 524288 65536 2
15 3500 524288 65536 2
16 3500 524288 65536 2
17 3500 524288 65536 2
18 3500 524288 65536 2
19 3500 524288 65536 2
20 3500 524288 65536 2
21 3500 524288 65536 2
22 3500 524288 65536 2
23 3500 524288 65536 2
24 3500 524288 65536 2
25 3500 524288 65536 2
26 3500 524288 65536 2
27 3500 524288 65536 2
28 3500 524288 65536 2
29 3500 524288 65536 2
30 3500 524288 65536 2
31 3500 524288 65536 2
32 3500 524288 65536 2
33 3500 524288 65536 2
34 3500 524288 65536 2
35 3500 524288 65536 2
36 3500 524288 65536 2
37 3500 524288 65536 2
38 3500 524288 65536 2
39 3500 524288 65536 2
40 3500 524288 65536 2
41 3500 524288 65536 2
Submit
Back to Top