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
sherlocklives:
2015-12-20 11:35:06
compilation error. compiling in system and ideone though :|
|
|
Dhawal Harkawat:
2015-11-06 06:54:37
AC..nlog^2n passes::D |
|
epsilon:
2015-10-21 10:22:38
may someone plz tell me what it means:
|
|
Vivek:
2015-07-23 13:29:06
nlogn solution : http://comscigate.com/Books/contests/icpc.pdf |
|
santamaria:
2015-07-06 12:34:19
Check For This
|
|
Chandrakanth :
2015-06-12 11:08:45
Wrong answer test #1. Isn't the first test case the one given in the example itself?If it is then my program gives the correct output 3. Last edit: 2015-06-12 11:10:17 |
|
anando_du:
2015-03-04 19:50:41
-_- are u kidding with me !!! wrong ans#1 ? |
|
mkrjn99:
2014-12-03 15:08:52
Binary search continues to amaze me! |
|
Sagar Shah:
2014-05-26 19:04:28
How to do this problem???
|
|
Ghost Of Perdition:
2014-01-27 12:55:15
N log^2 is getting TLE !!! |
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 |