LIS2VN - Another Longest Increasing Subsequence Problem

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/lis2vn


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 A1..An là một dãy con thỏa mãn với mọi i < j, Ai < Aj.

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 (x1, y1) được gọi là nhỏ hơn (x2, y2) nếu x1 < x2 y1 < y2.

Input

Dòng đầu chứa một số nguyên N (2 ≤ N ≤ 100000).

N dòng tiếp theo chứa N cặp số nguyên (xi, yi) (-109xi, yi ≤ 109).

Output

Chứa một số nguyên: độ dài của dãy con dài nhất của dãy đã cho.

Example

Input:
8
1 3
3 2
1 1
4 5
6 3
9 9
8 7
7 6

Output:
3

Bài gốc: http://www.spoj.com/problems/LIS2/.


Được gửi lên bởi:Race with time
Ngày:2009-04-13
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:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Jin Bin - SPOJ

hide comments
2019-09-24 05:00:12
hahaha bai de :v
duonght_pro_xinhgainhathemattroi_:)
2017-11-13 15:24:26
NlogN toan WA thoi
2017-01-04 15:21:33 John and the cows
Mọi người cho mình hỏi bài này có thuật O(NlogN) không? Nếu có thì cho mình xin tài liệu với.

Last edit: 2017-01-04 15:22:52
2014-12-02 17:57:27 livw
trong day co ton tai 2 cap giong nhau khong nhi?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.