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
Ravi Kiran:
2014-01-02 10:27:09
My N * log^2 N implementation passed with 0.38s (in case you are skeptical about the time limit). |
|
Ayush Nigam:
2013-08-29 17:03:26
my O(nlogn) is giving tle!!! |
|
Mukit09:
2013-08-02 20:04:23
Running...(4)
|
|
Bharath Reddy:
2013-07-02 06:45:18
O(n^2) won't work..
|
|
Master Wad7a:
2013-04-05 15:10:13
@problem setter: can u please tell me whats wrong with my last submission?? ID:9044708. I tried a lot of test cases but couldn't find whats wrong. |
|
Ninja coder:
2013-01-28 09:43:52
@Sparik: All test cases. I doubt even 1 will pass :P |
|
(Tjandra Satria Gunawan)(曾毅昆):
2012-10-06 18:06:03
wrong answer #1 means that you're getting wrong for case no:1 |
|
Saptarshi Chatterjee:
2012-10-06 16:18:00
"wrong answer #1 " what does this #1 means ? eoor in first output set or only 1 error ? |
|
alculquicondor:
2012-10-04 16:25:41
Solve NICEDAY first. |
|
a:
2012-09-20 16:41:05
will n^2 work...or an nlogn solution needs to be thought of?
|
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 |