Vòi Phun Nước

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John có một cánh đồng hình vuông kích thước $(N - 1) \times (N - 1)$ , với góc tây nam tại $(0, 0)$ và góc đông bắc tại $(N - 1, N - 1)$ . Trên cánh đồng có đúng $N$ vòi phun nước hai chiều đặt tại các tọa độ nguyên.

Mỗi vòi phun nước đặt tại tọa độ $(i, j)$ hoạt động như sau:

Tưới nước tất cả các điểm $(x, y)$ thỏa $x \geq i$ và $y \geq j$ (vùng đông bắc).
Bón phân tất cả các điểm $(x, y)$ thỏa $x \leq i$ và $y \leq j$ (vùng tây nam).

Một điểm $(x, y)$ với $0 \leq x, y \leq N - 1$ được coi là hợp lệ nếu nó vừa được tưới nước bởi ít nhất một vòi phun nước, vừa được bón phân bởi ít nhất một vòi phun nước.

Biết rằng mỗi hàng và mỗi cột đều có đúng một vòi phun nước (tức là các tọa độ $x$ của các vòi tạo thành một hoán vị của ${0, 1, \dots, N - 1}$ , và tương tự với các tọa độ $y$ ).

Hãy đếm số hình chữ nhật có các cạnh song song với trục tọa độ, có diện tích dương, với tất cả bốn góc đều là điểm hợp lệ (có tọa độ nguyên), và tất cả các điểm nguyên bên trong và trên biên của hình chữ nhật đều là điểm hợp lệ.

Nói cách khác, đếm số cặp điểm nguyên $(x_{1}, y_{1})$ và $(x_{2}, y_{2})$ với $0 \leq x_{1} < x_{2} \leq N - 1$ và $0 \leq y_{1} < y_{2} \leq N - 1$ sao cho toàn bộ hình chữ nhật $[x_{1}, x_{2}] \times [y_{1}, y_{2}]$ chỉ gồm các điểm hợp lệ.

Dữ liệu vào

Dòng đầu tiên: số nguyên $N$ ( $1 \leq N \leq 10^{5}$ ).
$N$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $i$ và $j$ ( $0 \leq i, j \leq N - 1$ ) là tọa độ của một vòi phun nước.
Đảm bảo mỗi hàng và mỗi cột có đúng một vòi phun nước.

Dữ liệu ra

In ra một số nguyên duy nhất: số hình chữ nhật hợp lệ, lấy modulo $10^{9} + 7$ .

Ràng buộc

$1 \leq N \leq 10^{5}$
Các vòi phun nước tạo thành một hoán vị: mỗi hàng và mỗi cột có đúng một vòi.

Ví dụ

Input	Output	Giải thích
5 0 4 1 1 2 2 3 0 4 3	21	Với $N = 5$ , có 21 hình chữ nhật hợp lệ. Ví dụ, hình chữ nhật $[0, 4] \times [0, 4]$ (toàn bộ cánh đồng) là hợp lệ.

Ghi chú

Đây là bài USACO 2018 January Platinum, bài 3.

Một hình chữ nhật $[x_{1}, x_{2}] \times [y_{1}, y_{2}]$ (với $x_{1} < x_{2}$ , $y_{1} < y_{2}$ ) hợp lệ khi và chỉ khi với mỗi cột $x \in [x_{1}, x_{2}]$ , tập hợp các $y$ hợp lệ trong cột đó chứa toàn bộ đoạn $[y_{1}, y_{2}]$ .

Bình luận

Không có bình luận tại thời điểm này.