Gửi bài giải
Điểm:
1,20 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho một dãy gồm N cặp số nguyên, tính độ dài của dãy con tăng dài nhất của nó.
Một dãy tăng ~A_{1}~ ...~A_{n}~ là một dãy con thỏa mãn với mọi ~i < j~, ~A_{i}~ ~<~ ~A_{j}~.
Một dãy con của một dãy số là một dãy số mà các phần tử của nó có cùng thứ tự với dãy đó, nhưng không cần liên tiếp.
Một cặp số nguyên (~x_{1}~, ~y_{1}~) được gọi là nhỏ hơn (~x_{2}~, ~y_{2}~) nếu ~x_{1}~ ~<~ ~x_{2}~ và ~y_{1}~ ~<~ ~y_{2}~.
Input
Dòng đầu chứa một số nguyên ~N~ (~2 \leq N \leq 100000~).
~N~ dòng tiếp theo chứa ~N~ cặp số nguyên (~x_{i}~, ~y_{i}~) ~(-10^9 \leq x_{i}, y_{i} \leq 10^9)~.
Output
- Chứa một số nguyên: độ dài của dãy con dài nhất của dãy đã cho.
Sample Input
8
1 3
3 2
1 1
4 5
6 3
9 9
8 7
7 6
Sample Output
3
Bình luận