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.
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).
The output contains an integer: the length of the longest increasing subsequence of the given sequence.
Input: 8 1 3 3 2 1 1 4 5 6 3 9 9 8 7 7 6 Output: 3
|Added by:||Bin Jin|
|Cluster:||Cube (Intel Pentium G860 3GHz)|
|Languages:||All except: C++ 4.9 SCM chicken|
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
-_- are u kidding with me !!! wrong ans#1 ?
Binary search continues to amaze me!
How to do this problem???
Ghost Of Perdition:
N log^2 is getting TLE !!!
My N * log^2 N implementation passed with 0.38s (in case you are skeptical about the time limit).
Last edit: 2014-01-12 19:24:24
my O(nlogn) is giving tle!!!
O(n^2) won't work..