记录编号	260853	评测结果	AAAAAAAAAA
题目名称	[Vijos1369] 难解的问题	最终得分	100
用户昵称	521	是否通过	通过
代码语言	C++	运行时间	0.084 s
提交时间	2016-05-14 16:07:56	内存使用	0.77 MiB

#include<stdio.h>
#include<string.h>
int a[300010]={0},b[300010]={0};
int search(int i,int len,int flag)
{
	int left=0,right=len,mid;
    while(left<right)
	{
		mid=left+((right-left)>>1);
		if(flag) 
		{
		  if(b[mid]<=a[i]) right=mid;
		  else left=mid+1;
		}
		else 
		{
		  if(b[mid]>=a[i]) right=mid;
		  else left=mid+1;
		}
    }
    return left;
}
int _521()
{
	freopen("muzuka.in","r",stdin);
	freopen("muzuka.out","w",stdout);
	int n,m,i,j,len1,len2;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)  scanf("%d",&a[i]);
	b[1]=a[m],len1=1;
	for(i=m-1;i>=1;i--)
	{
		if(b[len1]>a[i]) b[++len1]=a[i];
		else if((j=search(i,len1,1))!=1) b[j]=a[i];
	}
	memset(b,0,sizeof(b));
	b[1]=a[m],len2=1;
	for(i=m+1;i<=n;i++)
	{
		if(b[len2]<a[i]) b[++len2]=a[i];
		else if((j=search(i,len2,0))!=1) b[j]=a[i];
	}
	printf("%d\n",len1+len2-1);
    return 0;
}
int _520=_521();
int main(){;}