레이팅 미적용JOI 君は,砂浜で砂の城を作って遊んだ.JOI 君が作った城は,砂浜のある長方形の領域に含まれている.
この長方形の領域は縦H 行,横W 列に区切られたマス目として表され,縦方向は南北方向に平行であり,
横方向は東西方向に平行である.北からi 行目(\(1 \le i \le H\)),西からj 列目(\(1 \le j \le W\)) のマスの高さはAi,j
である.ただし,Ai,j の値はすべて相異なる.
この砂の城に対し,JOI 君は以下の行動を行った.
1. あるマスを選び,そのマスの上からスタートする.
2. その後,東西南北に隣接するより低いマスの上に移動することを,0 回以上繰り返す.
最終的にJOI 君が訪れたマスの領域を上から見ると,これは1 つの長方形で表された.
各マスの高さAi, j の情報が与えられたとき,JOI 君が訪れたマスの長方形領域としてあり得るものが何通
りあるかを求めるプログラムを作成せよ.
• \(H \ge 1\).
• \(W \ge 1\).
• H × W ≦50 000.
• 1 ≦Ai, j ≦10 000 000 (\(1 \le i \le H,1 \le j \le W\)).
• Ai1,j1 , Ai2,j2 (\(1 \le i1 \le H,1 \le j1 \le W,1 \le i2 \le H,1 \le j2 \le W\),(i1, j1) , (i2, j2)).
- (9 点) H = 1.
- (10 点) H × W ≦100.
- (5 点) H × W ≦1 500.
- (56 点) H × W ≦7 000.
- (20 点) 追加の制約はない.
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
H W
A1,1 A1,2 · · · A1,W
A2,1 A2,2 · · · A2,W
...
AH,1 AH,2 · · · AH,W
標準出力に,JOI 君が訪れたマスの長方形領域としてあり得るものが何通りあるかを,1 行で出力せよ.
第21 回日本情報オリンピック(JOI 2021/2022) 本選
2022 年2 月13 日(オンライン開催)
1 5
2 4 7 1 5
10
3 2
18 10
19 12
17 13
15
3 5
83 47 36 38 40
13 10 26 68 67
15 19 20 70 90
65