P7149 [USACO20DEC] Rectangular Pasture S

Farmer John’s largest pasture can be viewed as a huge two-dimensional grid made of square cells (imagine a huge chessboard). Now, there are $N$ cows occupying some of the cells ($1 \le N \le 2500$). Farmer John wants to build a fence that encloses a rectangular region; this rectangle must have its four sides parallel to the $x$-axis and the $y$-axis, and it must contain at least one cell. Please help him compute the number of different subsets of cows that he can enclose in such a region. Note that the empty set should be counted as one of the answers.

The first line of input contains an integer $N$. The next $N$ lines each contain two space-separated integers, indicating the coordinates $(x,y)$ of the cell occupied by a cow. All $x$ coordinates are distinct, and all $y$ coordinates are distinct. All values of $x$ and $y$ are in the range $0 \ldots 10^9$.

Output the number of subsets of cows that FJ can enclose. It can be proven that this number fits in a 64-bit signed integer type (for example, `long long` in C/C++).

There are $2^4$ subsets in total. FJ cannot build a fence that encloses only cows $1$, $2$, and $4$, or only cows $2$ and $4$, or only cows $1$ and $4$, so the answer is $2^4 - 3 = 16 - 3 = 13$. - Testdata 2-3 satisfy $N \le 20$. - Testdata 4-6 satisfy $N \le 100$. - Testdata 7-12 satisfy $N \le 500$. - Testdata 13-20 have no additional constraints. Problem by: Benjamin Qi. Translated by ChatGPT 5