## Magic Forest

View as PDF

Points: 0.70 (partial)
Time limit: 1.5s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

In order to escape from the hustle and bustle of the city, Loc decided to spend his entire summer vacation exploring the forest on the outskirts of his hometown. To fully immerse himself in the natural environment, Loc needs to build a house in the forest and live there for the entire summer vacation.

The forest can be described by a rectangular grid consisting of ~n~ rows and ~m~ columns. The rows are numbered from ~1~ to ~n~ from north to south, and the columns are numbered from ~1~ to ~m~ from west to east. The cell located at row ~i~ and column ~j~ is denoted as cell ~(i, j)~. Strangely, each cell on the rectangular grid contains exactly one oak tree, and the tree at cell ~(i, j)~ has a height of ~h_{i,j}~.

Loc's house-building plan will begin with the construction of a fence surrounding the house. First, Loc needs to choose four oak trees located at cells ~(r_1, c_1)~, ~(r_1, c_2)~, ~(r_2, c_1)~, and ~(r_2, c_2)~ such that ~1 \le r_1 < r_2 \le n~ and ~1 \le c_1 < c_2 \le m~. In other words, the four chosen cells will be the four corners of a rectangle with the upper left corner at cell ~(r_1, c_1)~ and the lower right corner at cell ~(r_2, c_2)~. Moreover, after Loc cuts down the trees, the resulting fence must form a closed shape.

Loc's tree-cutting plan, and the corresponding conditions to ensure that the resulting fence forms a closed shape, are as follows:

• Cut down the tree at cell ~(r_1, c_1)~ and let it fall to the east. The tree at cell ~(r_1, c_1)~ must have a height at least ~c_2 - c_1~.

• Cut down the tree at cell ~(r_1, c_2)~ and let it fall to the south. The tree at cell ~(r_1, c_2)~ must have a height at least ~r_2 - r_1~.

• Cut down the tree at cell ~(r_2, c_2)~ and let it fall to the west. The tree at cell ~(r_2, c_2)~ must have a height at least ~c_2 - c_1~.

• Cut down the tree at cell ~(r_2, c_1)~ and let it fall to the north. The tree at cell ~(r_2, c_1)~ must have a height at least ~r_2 - r_1~.

To consider the selection of the oak trees that need to be cut down, Loc needs to know how many ways there are to choose a set of four trees that satisfy the above requirements. Please help Loc with this task.

#### Input

The first line contains two positive integers ~n~ and ~m~ (~2 \leq n, m~; ~n \times m \leq 80\,000~) — the size of the rectangular grid describing the forest.

The ~i~-th of the ~n~ following lines contains ~m~ integers ~h_{i,1}, h_{i,2}, \ldots, h_{i,m}~ (~1 \le h_{i,j} \le 10^9~) — the heights of the trees in the forest.

#### Output

Print the total number of ways to choose a set of four trees that satisfy the requirements of the problem.

#### Scoring

1 500 ~n\times m \le 1000~
2 750 ~h_{i, j} \le 10~ for all ~1 \le i \le n, 1 \le j \le m~
Total 2500

#### Sample Input 1

2 4
4 3 2 1
1 2 3 4


#### Sample Output 1

6


#### Sample Input 2

3 4
3 1 2 2
1 2 1 2
2 2 1 3


#### Sample Output 2

9


#### Sample Input 3

4 3
3 1 2
1 2 2
2 1 1
2 2 3


#### Sample Output 3

10


#### Notes

In the first example, all sub-rectangles have four corners that satisfy the tree-cutting requirements.

In the second example, in addition to the ~6~ sub-rectangles of size ~2 \times 2~, there are ~3~ ways to choose a set of four trees as follows:

Illustration for the second example.