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 A_{1}..A_{n} is a sequence such that for every i < j, A_{i} < A_{j}.
A subsequence of a sequence is a sequence that appears in the same relative order, but not necessarily contiguous.
A pair of integers (x_{1}, y_{1}) is less than (x_{2}, y_{2}) iff x_{1} < x_{2} and y_{1} < y_{2}.
Input
The first line of input contains an integer N (2 ≤ N ≤ 100000).
The following N lines consist of N pairs of integers (x_{i}, y_{i}) (10^{9} ≤ x_{i}, y_{i} ≤ 10^{9}).
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
mahmud2690:
20180420 17:03:30
2DBIT >> 2DSegment tree... 

Md. Najim Ahmed:
20171229 00:51:53
solved it n(log2n)^2 with 2d bit and grid compression ... 

alexyu:
20171110 08:33:47
Last edit: 20171207 11:59:30 

rihaz_zahir:
20170201 16:08:51
@theph0enix, (1, 3) is not less than (2, 3), that all we care, even if (2, 3) comes before (1, 3) we would say (2, 3) is not less than (1, 3) Last edit: 20170201 16:11:23 

rogerioagjr:
20160721 03:28:19
TLE O(n*log(n)^2) :/ 

mkfeuhrer:
20160629 22:11:58
dp gives tle !! LIS dp wont work! 

theph0enix:
20160224 07:25:28
How do we compare (1, 3) and say (2, 3) since by the given definition of inequality these two pairs are neither less nor greater than the other. They cant even be considered equal since (1,3) is less than (2, 4) but (2, 4) is again neither less nor greater than (2, 3). 

abhishekrahul:
20151221 05:28:01
what it means TLE #3 ???


sherlocklives:
20151220 11:35:06
compilation error. compiling in system and ideone though :


Dhawal Harkawat:
20151106 06:54:37
AC..nlog^2n passes::D 
Added by:  Bin Jin 
Date:  20080120 
Time limit:  0.345s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: CPP 