记录编号	38468	评测结果	AAAAAAAAAA
题目名称	[SOJ 1137] 河床	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2012-04-19 14:43:15	内存使用	1.27 MiB

/*
method:优先队列
prob:riverbed
*/
#include <fstream>
using namespace std;
ifstream fin("riverbed.in");
ofstream fout("riverbed.out");
int n,k,A[50000],Tk=1;
class pq
{
public:
	int Data[50000],Ti[50000],head,tail;
	pq()
	{
		head=1;tail=0;
	}
	void up()
	{
		while(Ti[head]<Tk && head<tail)
			head++;
	}
	void pushback(int Tar,int Pos,int type)
	{
		while(Ti[head]<Tk && head<tail)
			head++;
		if(type==1)
			while(Tar>Data[tail] && head<=tail)
				tail--;
		if(type==2)
			while(Tar<Data[tail] && head<=tail)
				tail--;
		tail++;
		Ti[tail]=Pos;
		Data[tail]=Tar;
	}
}Max,Min;
void Initialize()
{
int i;
	fin>>n>>k;
	for(i=1;i<=n;i++)
		fin>>A[i];
}

void pq()
{
int i=1,Mx=-2000000;
	for(;i<=n;)
	{
		Max.pushback(A[i],i,1);
		Min.pushback(A[i],i,2);
		while(Max.Data[Max.head]-Min.Data[Min.head] >k)
			{Tk++;Max.up();Min.up();}
		if(i-Tk+1>Mx)
			Mx=i-Tk+1;
		i++;
	}
	fout<<Mx<<endl;
}

int main()
{
	Initialize();
	
	pq();
	
	fin.close();
	fout.close();
	return 0;
}