LIS2 - Another Longest Increasing Subsequence Problem
Given a sequence of N pairs of integers, find the length of the longest increasing subsequence of it.
An increasing sequence A1..An is a sequence such that for every i < j, Ai < Aj.
A subsequence of a sequence is a sequence that appears in the same relative order, but not necessarily contiguous.
A pair of integers (x1, y1) is less than (x2, y2) iff x1 < x2 and y1 < y2.
Input
The first line of input contains an integer N (2 ≤ N ≤ 100000).
The following N lines consist of N pairs of integers (xi, yi) (-109 ≤ xi, yi ≤ 109).
Output
The output contains an integer: the length of the longest increasing subsequence of the given sequence.
Example
Input: 8 1 3 3 2 1 1 4 5 6 3 9 9 8 7 7 6 Output: 3
hide comments
Huỳnh Quang Thảo:
2011-07-20 12:11:07
I think this problem same as LIS. But I AC and has wrong answer, anyone help me why ? |
|
Graphis_:
2011-07-17 03:58:28
Administrator:My program works fine on my computer.I succeded in compiling it using G++ 3.4.5,4.3.4,4.4.2,and 4.5.2.
|
|
Hy Trường Sơn:
2011-07-17 03:58:28
nice problem! |
|
Eric Alejandro Destefanis:
2011-07-17 03:58:28
I cant sleep... i cant get this problem out of my head haha, any little hints? (apart from using LIS) |
Added by: | Bin Jin |
Date: | 2008-01-20 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: CPP |