페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5862
서브태스크

모래성 2 4초 1024MB

문제

JOI 너는 모래 해변에서 모래 성을 만들고 놀았다. JOI가 만든 성은 모래 사장이있는 직사각형 영역에 포함되어 있습니다.

이 직사각형의 영역은 세로 H 행, 가로 W 열로 구분 된 매스 눈으로 표시되고, 세로 방향은 남북 방향에 평행하고, 횡 방향은 동서 방향에 평행이다. 북쪽에서 i 행째 (1 ≤ i ≤ H), 서쪽에서 j 열째 (1 ≤ j ≤ W)의 칸의 높이는 A_{i, j}입니다. 그러나 A_{i, j}의 모든 값은 다릅니다.

이 모래 성에 대해 JOI는 다음과 같은 행동을했습니다.

1. 한 매스를 선택하고 그 매스 위에서 시작합니다.

2. 그 후 동서남북에 인접한 더 낮은 매스 위로 이동하는 것을 0회 이상 반복한다.

결국 JOI가 방문한 송어의 영역을 위에서 보았을 때 이것은 하나의 직사각형으로 표현되었습니다.

각 매스의 높이 A_{i, j}의 정보가 주어졌을 때, JOI군이 방문한 매스의 직사각형 영역으로서 있을 수 있는 것이 몇개인가 있는지를 요구하는 프로그램을 작성하라.


입력

입력은 다음 형식으로 표준 입력에서 제공됩니다. 입력 된 모든 값은 정수입니다.

H W

A_{1,1} A_{1,2} \dots A_{1,W}

A_{2,1} A_{2,2} \dots A_{2,W}

.

.

.

A_{H,1} A_{H,2} \dots A_{H,W}

제약

• H ≧ 1.

• W ≧ 1.

• H × W ≤ 50\, 000.

• 1 ≤ A_{i, j} ≤ 10\, 000\, 000 (1 ≤ i ≤ H, 1 ≤ j ≤ W).

• A_{i1, j1} \neq A_{i2, j2} (1≤i1≤H, 1≤j1≤W, 1≤i2≤H, 1≤j2≤W, (i1, j1) \neq (i2, j2)).


출력

표준 출력에, JOI 군이 방문한 매스의 직사각형 영역으로서 있을 수 있는 것이 몇개인가 있는 것을, 1 행으로 출력하라.


부분문제

번호 점수 조건
#19점

H = 1.

#210점

H × W ≤ 100.

#35점

H × W ≤ 1 500.

#456점

H × W ≤ 7 000.

#520점

추가 제약이 없다.


예제1

입력
15
24715
출력
10

JOI 군이 방문한 매스의 직사각형 영역으로서, 이하의 10가지가 있을 수 있기 때문에, 10을 출력한다.

이 입력 예제는 모든 작은 문제의 제약을 충족시킵니다.


예제2

입력
32
1810
1912
1713
출력
15

JOI군이 방문한 셀에 의해 형성될 수 있는 직사각형은 15이므로 15를 출력합니다.


예제3

입력
35
8347363840
1310266867
1519207090
출력
65

예를 들어, JOI군이 방문한 셀에 의해 다음과 같은 직사각형이 형성될 수 있습니다. 총 65 가능한 직사각형이 있으므로 65를 출력합니다.


출처

JOI 2022

역링크