bzoj#P2225. [SPOJ] LIS2 - Another Longest Increasing Subsequence Problem

[SPOJ] LIS2 - Another Longest Increasing Subsequence Problem

题目描述

给定 NN 个数对 (xi,yi)(x_i, y_i),求最长上升子序列的长度。上升序列定义为 {(xi,yi)}\{(x_i, y_i)\} 满足对 i<ji\lt jxi<xjx_i\lt x_jyi<yjy_i\lt y_j

输入格式

第一行一个整数 nn,接下来 nn 行,每行两个整数 xi,yix_i,y_i

输出格式

8 
1 3 
3 2 
1 1 
4 5 
6 3 
9 9 
8 7 
7 6 

3

提示

2n105,109xi,yi1092\le n \le 10^5,-10^9\le x_i,y_i\le 10^9

题目来源

没有写明来源