QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 1024 MB
[-1]

# 3005. Monotony

Statistics

Problem Description

You are given an r×c grid. Each cell of this grid is filled with a number between 1 and r×c inclusive, and each cell’s number is distinct.

Define a grid of numbers to be monotonic if each row and column is either increasing or decreasing (this can be different for each row or column).

Define a subgrid of the grid as follows: First choose some nonempty subset of the rows and columns. Next, take elements that lie in both the chosen rows and columns in the same order.

There are (2r1)(2c1) nonempty subgrids of the given grid. Of these subgrids, count how many are monotonic.

Consider this grid:

125764983

There are nine 1×1 subgrids, nine 1×2’s, three 1×3’s, nine 2×1’s, nine 2×2’s, three 2×3’s, three 3×1’s, three 3×2’s, and one 3×3. They are all monotonic, for 9+9+3+9+9+3+3+3+1=49 monotonic subgrids.

Input

Each test case will begin with a line with two space-separated integers r and c (1r,c20), which are the dimensions of the grid.

Each of the next r lines will contain c space-separated integers x (1xrc, all x’s are unique). This is the grid.

Output

Output a single integer, which is the number of monotonic subgrids in the given grid

Samples

Sample Input 1

3 3
1 2 5
7 6 4
9 8 3

Sample Output 1

49

Sample Input 2

4 3
8 2 5
12 9 6
3 1 10
11 7 4

Sample Output 2

64