记录编号	471238	评测结果	AAAAAAAAAA
题目名称	[NOIP 2013]花匠	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	1.916 s
提交时间	2017-11-06 08:47:19	内存使用	1.46 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
inline int read(){
	int sum(0);char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
struct node{
	node *lch,*rch;
	int mx;
	node():lch(NULL),rch(NULL),mx(0){}
	inline void pushup(){this->mx=max(this->lch->mx,this->rch->mx);}
}*root[2];
inline void build(int l,int r,node *&x){
	x=new node;if(l==r)return;int mid((l+r)>>1);
	build(l,mid,x->lch);build(mid+1,r,x->rch);
}
inline void update(int pos,int w,int l,int r,node *x){
	if(l==r){x->mx=w;return;}int mid((l+r)>>1);
	if(pos<=mid)update(pos,w,l,mid,x->lch);
	else update(pos,w,mid+1,r,x->rch);
	x->pushup();
}
inline int query(int ll,int rr,int l,int r,node *x){
	if(ll<=l&&r<=rr)return x->mx;int mid((l+r)>>1),ret(0);
	if(ll<=mid)ret=query(ll,rr,l,mid,x->lch);
	if(mid<rr)ret=max(ret,query(ll,rr,mid+1,r,x->rch));
	return ret;
}
const int size(1000000);
int n;
int h[100005],f[100005][2];
int main(){
	freopen("FlowerNOIP2013.in","r",stdin);freopen("FlowerNOIP2013.out","w",stdout);
	n=read();build(0,size,root[0]);build(0,size,root[1]);
	for(int i=1;i<=n;++i)h[i]=read();
	f[1][0]=f[1][1]=1;update(h[1],1,0,size,root[0]);update(h[1],1,0,size,root[1]);
	for(int i=2;i<=n;++i){
		if(h[i]){
			f[i][0]=query(0,h[i]-1,0,size,root[1])+1;
			update(h[i],f[i][0],0,size,root[0]);
		}
		if(h[i]<size){
			f[i][1]=query(h[i]+1,size,0,size,root[0])+1;
			update(h[i],f[i][1],0,size,root[1]);
		}
	}
	printf("%d",max(query(0,size,0,size,root[0]),query(0,size,0,size,root[1])));
}