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

#5862
서브태스크

모래성 2 4s 1024MB

문제

정올이는 가로 W열, 세로 H행으로 이루어진 모래밭 위에 모래 성을 만들었다. 각 칸의 높이는 서로 다른 정수 A_{i,j}로 주어진다 (1 ≤ i ≤ H, 1 ≤ j ≤ W).

정올이는 다음과 같은 방식으로 모래 성 위를 이동한다:

  1. 아무 칸 하나를 출발점으로 선택한다.

  2. 현재 칸에서 동·서·남·북으로 인접한 높이가 더 낮은 칸으로 이동하는 과정을 0회 이상 반복한다.

이때 정올이가 최종적으로 방문한 모든 칸의 집합을 위에서 바라보면 언제나 속이 꽉 찬 하나의 직사각형을 이룬다.

주어진 높이 배열 A에 대해, 정올이가 방문한 칸들의 영역으로 만들 수 있는 직사각형의 개수를 구하라.


입력

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

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)).


출력

첫 줄에 정올이가 방문한 칸들의 영역으로 만들 수 있는 직사각형의 개수를 출력한다.


부분문제

번호 점수 조건
#19점

H = 1

#210점

H × W ≤ 100

#35점

H × W ≤ 1 500

#456점

H × W ≤ 7 000

#520점

추가 제약 조건 없음


예제 #1

1 5
2 4 7 1 5
10

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


예제 #2

3 2
18 10
19 12
17 13
15

예제 #3

3 5
83 47 36 38 40
13 10 26 68 67
15 19 20 70 90
65

출처

JOI 2022

로그인해야 코드를 작성할 수 있어요.