| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P171PROD - ROUND 1D - Sự kiện lịch sử |
Ryze rất thích học và rất siêng năng làm bài tập về nhà của mình. Ryze học rất giỏi các môn khoa học tự nhiên. Tuy nhiên cậu lại gặp rất nhiều vấn đề ở môn lịch sử.
Lịch sử thế giới bao gồm đúng N sự kiện. Sự kiện thứ i được bắt đầu từ năm ai và kết thúc vào năm bi (ai < bi). Ryze dễ dàng nhớ được các sự kiện lịch sử (Ryze được thừa hưởng trí nhớ tuyệt vời của bố cậu). Tuy nhiên giáo viên dạy lịch sử của cậu – cô giáo fiora đã giao cho cậu một bài tập khó hơn. Giáo viên của Ryze cho rằng sự kiện j chứa đựng sự kiện i nếu aj < ai và bj > bi. Nhiệm vụ của bạn là tìm số sự kiện được chứa đựng trong một số sự kiện khác.
Input
Dòng đầu chứa số nguyên N (1 <= n <= 10^5) là sô sự kiện xảy ra trong lịch sử.
N dòng tiếp theo, dòng thứ i + 1 chứa 2 số nguyên ai và bi (1 <= ai < bi <= 10^9) là thời gian bắt đầu và kết thúc của sự kiện thứ i.
Output
Số nguyên duy nhất là đáp án.
Example
Test 1:
Input:
5
2 11
3 10
4 9
5 8
6 7
Output:
4
Test 2:
Input:
5
2 200
2 50
50 101
57 88
20 70
Output:
3
Test 3:
Input:
1
1 1000000
Output:
0
| Được gửi lên bởi: | adm |
| Ngày: | 2017-02-17 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
