직사각형

19세기 초, 호세인굴루 칸 사르다르는 강이 내려다보이는 평원에 궁전을 지으라고 명령했다. 평원은 $n \times m$ 격자로 나타낸다. 행은 $0$번부터 $n-1$번까지, 열은 $0$번부터 $m-1$번까지 번호가 붙는다. 행 $i$, 열 $j$의 칸을 $(i,j)$라 하고 높이를 $a[i][j]$라 한다.

건축가들은 궁전을 지을 직사각형 영역을 골라야 한다. 영역은 격자의 경계인 $0$번 행, $n-1$번 행, $0$번 열, $m-1$번 열의 칸을 포함할 수 없다. 네 정수 $r_1,r_2,c_1,c_2$ ($1 \leq r_1 \leq r_2 \leq n-2$, $1 \leq c_1 \leq c_2 \leq m-2$)를 골라 $r_1 \leq i \leq r_2$이고 $c_1 \leq j \leq c_2$인 모든 칸 $(i,j)$를 영역으로 삼는다.

영역 안의 모든 칸 $(i,j)$에 대해 다음 조건이 성립하면 그 영역은 올바르다.

• 행 $i$에서 영역에 인접한 두 칸 $(i,c_1-1)$, $(i,c_2+1)$과 열 $j$에서 영역에 인접한 두 칸 $(r_1-1,j)$, $(r_2+1,j)$의 높이가 모두 $a[i][j]$보다 엄격히 크다.

올바른 영역의 수를 구하여라.

구현 세부 사항

다음 함수를 구현해야 한다.

long long count_rectangles(vector<vector<int>> a)

• $a$: 각 칸의 높이를 나타내는 $n \times m$ 정수 배열
• 올바른 영역의 수를 반환해야 한다.

예제

count_rectangles([[4,  8,  7,  5,  6],
                  [7,  4, 10,  3,  5],
                  [9,  7, 20, 14,  2],
                  [9, 14,  7,  3,  6],
                  [5,  7,  5,  2,  7],
                  [4,  5, 13,  5,  6]])

올바른 영역은 다음 여섯 개다.

• $r_1=r_2=c_1=c_2=1$
• $r_1=1$, $r_2=2$, $c_1=c_2=1$
• $r_1=r_2=1$, $c_1=c_2=3$
• $r_1=r_2=4$, $c_1=2$, $c_2=3$
• $r_1=r_2=4$, $c_1=c_2=3$
• $r_1=3$, $r_2=4$, $c_1=c_2=3$

예를 들어 $r_1=1$, $r_2=2$, $c_1=c_2=1$인 영역에서 $a[1][1]=4$는 $a[0][1]=8$, $a[3][1]=14$, $a[1][0]=7$, $a[1][2]=10$보다 작고, $a[2][1]=7$도 $a[0][1]=8$, $a[3][1]=14$, $a[2][0]=9$, $a[2][2]=20$보다 작다.

제한

• $1 \leq n,m \leq 2500$
• 모든 $i,j$에 대해 $0 \leq a[i][j] \leq 7\,000\,000$

부분 문제

1. (8점) $n,m \leq 30$
2. (7점) $n,m \leq 80$
3. (12점) $n,m \leq 200$
4. (22점) $n,m \leq 700$
5. (10점) $n \leq 3$
6. (13점) 모든 $i,j$에 대해 $0 \leq a[i][j] \leq 1$
7. (28점) 추가 제한이 없다.

• 첫째 줄: $n\;m$
• 이어지는 $n$개 줄의 $i$번째 줄: $a[i][0]\;a[i][1]\;\ldots\;a[i][m-1]$

• count_rectangles의 반환 값을 한 줄에 출력한다.