记录编号	241351	评测结果	AAAAAAAAAA
题目名称	[NOIP 1999]拦截导弹	最终得分	100
用户昵称	Hzoi_Yniverse	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2016-03-25 09:54:13	内存使用	1.46 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[100000],f[100000],b[100000],n=0;;
int Q1();
int Q2();
int Find1(int,int,int);
int Find2(int,int,int);
int main(){
	freopen("missile.in","r",stdin);
	freopen("missile.out","w",stdout);
	while(scanf("%d",&a[++n])!=EOF);n--;
	printf("%d\n%d",Q1(),Q2());
	return 0;
}
int Q1(){
	int max=0;memset(b,0,sizeof(b));b[0]=0x7f7f7f7f;
	for(int i=1;i<=n;i++){
		int site=Find1(a[i],0,i);
		f[i]=site;
		b[site]=a[i];
		if(max<f[i]) max=f[i];
	}
	return max;
}
int Q2(){
	memset(f,0,sizeof(f));
	int max=0;memset(b,0x7f,sizeof(b));b[0]=0;
	for(int i=1;i<=n;i++){
		int site=Find2(a[i],0,i);
		f[i]=site;
		b[site]=a[i];
		if(max<f[i]) max=f[i];
	}
	return max;
}
int Find1(int h,int l,int r){
	while(l<=r){
	    int mid=(l+r)>>1;
		if(b[mid]>=h) l=mid+1;
		else r=mid-1;
	}
	return l;
}
int Find2(int h,int l,int r){
	while(l<=r){
		int mid=(l+r)>>1;
		if(b[mid]>=h) r=mid-1;
		else l=mid+1;
	}
	return l;
}