HSG12 Hà Nội 2026 - Thanh kiếm

Xem dạng PDF

Gửi bài giải

Điểm: 17,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong 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

Hãy đọc nội quy trước khi bình luận.


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