200分WA记录

code

#include <iostream>
#include <string>
using namespace std;
string s;
int n=1,a[100010],dp[100010],cnt=1,f[100010]; 
int main(){
	getline(cin,s);
	for(int i=0;i<s.size();i++){
		if(s[i]>='0'&&s[i]<='9')
			a[n]=a[n]*10+s[i]-'0';
		else n++;
	}
	dp[1]=a[1];
	for(int i=2;i<=n;i++){
		if(a[i]<=dp[cnt])dp[++cnt]=a[i];
		else{
			int l=1,r=cnt,mid;
			while(l<r){
				mid=(l+r)>>1;
				if(dp[mid]<a[i])r=mid;
				else l=mid+1;
			}
			dp[l]=a[i];
		}
	}
	cout<<cnt<<endl;
	cnt=1; f[1]=a[1];
	for(int i=2;i<=n;i++){
		if(a[i]>f[cnt])f[++cnt]=a[i];
		else{
			int l=1,r=cnt,mid;
			while(l<=r){
				mid=(l+r)>>1;
				if(f[mid]>=a[i])r=mid-1;
				else l=mid+1;
			}
			f[l]=a[i];
		}
	}
	cout<<cnt;
	return 0;
}