Cho một chuồng rộng vô hạn được biểu diễn dưới dạng lưới 2D. Có một tập hợp lớn gồm $N$ con bò, con bò thứ $i$ đứng ở hàng xixi​ cột yiyi​ (ký hiệu là ô (xi,yi)(xi​,yi​)).

Một cách đặt hàng rào sẽ bao đóng trọn vẹn một vùng chữ nhật các ô, với các cạnh phải song song với trục $x$ và $y$, vùng có thể nhỏ tới mức chỉ bao gồm một ô.

Với một cách đặt hàng rào, có thể dựng nên một tập hợp con các con bò nằm trong hàng rào.

Đếm số tập con khác nhau của tập hợp lớn có thể xây dựng bằng cách đặt hàng rào như trên.

Dữ liệu đầu vào

• Dòng đầu tiên chứa số $N$ $(1\le N\le 2500)$.
• $N$ dòng tiếp theo, dòng thứ $i$ chứa hai số xi,yixi​,yi​ (0≤xi,yi≤109)(0≤xi​,yi​≤109)

Định dạng đầu ra

• In ra số tập con khác nhau có thể dựng được

Điểm số

• Test 1 là test ví dụ
• Test 2-3 thỏa mãn $N\le 20$
• Test 4-6 thỏa mãn $N\le 100$
• Test 7-12 thỏa mãn $N\le 500$
• Test 13-20 không có điều kiện nào khác.

Ví dụ

Ví dụ 1

Đầu vào4 0 2 1 0 2 3 3 5Đầu raGiải thích

Có 2424 tập con của tập hợp 4 con bò.
Không thể xây dựng hàng rào chỉ chứa ba con bò 1-2-4, hoặc chỉ chứa hai con bò 2 và 4, hoặc chỉ chứa bò 4, nên đáp án là 24−3=1324−3=13

0ThíchBình luậnLưuChia sẻBáo cáo
Bài tập gợi ý:

•  Bài 02: Thi online
•  Phân tích #4
•  Chia hết #1
•  [HSG 9] Tổng chữ số
•  USACO 2022 December Contest, Bronze, Feeding the Cows
•  USACO 2022 US Open Contest, Bronze, Photoshoot
•  [Vector]. Bài 2. Erase Insert
•  [Vector]. Bài 6. max_element, min_element, accumulate

proudly powered by DMOJ| developed by LQDJudge team                                         Tiếng Việt (vi)                                                           English (en)