#BZOJ3927. Improvements
-
ID: 2495
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
Improvements
No submission language available for this problem.
题目描述
给出一个1到N的全排列，要求选出一个尽可能长的子序列，满足
1：不存在两个数0<=i<j<N满足线段Min(A(i),A(i+1)),Max(A(i),A(i+1))
和线段Min(A(j),A(j+1),Max(A(j),A(j+1))有交但不互相包含。
2：A(0)一直为0.
例如1 5 3 4和1 5 3 2是两个合法方案并且在后面加上任意一个数都将导致不合法。3 5 1不合法是因为[0,3]和[1,5]相交但不互相包含。
N<=200000
输入格式
如题
输出格式
如题
input 1 4 1 3 2 4 input 2 4 1 4 2 3
output 1 3 output 2 4
数据范围与约定
第一个样例把3去掉以后就合法了
第二个样例没有冲突 直接输出4