Sắp xếp thí sinh
Đề bài
Mô tả
Cho bảng xếp hạng hai vòng thi của thí sinh trong một kỳ thi ACM/ICPC. Ta chắc chắn Elo của thí sinh cao hơn Elo của thí sinh khi xếp hạng cao hơn ở cả hai vòng, tức là và , trong đó là thứ hạng của ở vòng và vòng (tương tự với ). Trong các trường hợp còn lại thì không chắc chắn.
Hãy đếm số cách chọn ra thí sinh sao cho có thể sắp xếp thí sinh này theo thứ tự Elo giảm dần một cách chắc chắn (mọi cặp thí sinh được chọn đều so sánh chắc chắn được với nhau).
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và (, ) là số thí sinh và số thí sinh cần chọn.
Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và () là thứ hạng của thí sinh thứ ở vòng và vòng . Các thứ hạng trong cùng một vòng đôi một khác nhau.
Dữ liệu ra
In ra một số nguyên là số cách chọn. Dữ liệu đảm bảo đáp án không vượt quá .
Ràng buộc
- , .
- ; các đôi một khác nhau, các đôi một khác nhau.
- Đáp án không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 3 2 2 1 1 3 3 5 4 4 5 |
7 | Có cách chọn thí sinh; chỉ cách chọn có cả hai thí sinh cuối (hạng và , không so sánh được) là không hợp lệ. |
| 3 2 1 1 2 3 3 2 |
2 | Thí sinh hơn hai thí sinh còn lại; thí sinh và không so sánh được. |
Bình luận