HSG12 Hà Nội 2026 - Thanh kiếm
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Trong một trò chơi nhập vai, người chơi thu thập được ~N~ thanh kiếm được đánh số từ ~1~ tới ~N~. Mỗi thanh kiếm ~i~ có chỉ số tấn công ~a_i~ và chỉ số phòng thủ ~b_i~. Quy tắc để phân loại các thanh kiếm như sau:
Một thanh kiếm ~i~ bị coi là vô dụng (bị thống trị hoàn toàn) nếu tồn tại một thanh kiếm ~j~ khác ~(j \ne i)~ sao cho: ~a_j \ge a_i~ và ~b_j \ge b_i~;
Ngược lại, nếu không tồn tại bất kỳ thanh kiếm ~j~ nào thống trị được thanh kiếm ~i~ theo cả hai chỉ số như trên thì thanh kiếm ~i~ được coi là hữu dụng.
Biết rằng không có hai thanh kiếm nào trùng nhau cả hai chỉ số (tức là không tồn tại ~i \ne j~ sao cho ~a_i = a_j~ và ~b_i = b_j~).
Yêu cầu: Hãy đếm số lượng thanh kiếm hữu dụng.
Input
Dòng đầu tiên chứa một số nguyên dương ~N~ ~(1 \le N \le 10^5)~;
~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~a_i, b_i~ ~(1 \le a_i, b_i \le 10^9)~ lần lượt là chỉ số tấn công và phòng thủ của thanh kiếm thứ ~i~.
Output
- Một số nguyên dương là kết quả bài toán.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~80\%~ | ~N \le 1000~ |
| 2 | ~20\%~ | Không có giới hạn gì thêm |
Sample Input 1
4
3 2
2 4
4 1
1 3
Sample Output 1
3
Notes
Thanh kiếm ~1, 2, 3~ là hữu dụng;
Thanh kiếm ~4~ ~(1, 3)~ bị thanh kiếm ~2~ ~(2, 4)~ thống trị hoàn toàn vì ~2 \ge 1~ và ~4 \ge 3~ ~\rightarrow~ Vô dụng.
Bình luận