记录编号	333420	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	Zwoi_只会打表抄代码的蒟蒻	是否通过	通过
代码语言	C	运行时间	1.435 s
提交时间	2016-10-30 18:51:29	内存使用	26.99 MiB

#include <stdio.h>
typedef struct line
{
	int num,book;
}A;
A b[1000010],c[1000010];
int i,n,k,et,ft,eh,fh,bb[1000010],cc[1000010],b1,a[1000010],c1;
int main()
{
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;i++)
		scanf("%d",a+i);
	eh=fh=b1=c1=1;
	et=ft=2;
	b[1].num=0x7f7f7f7f;//最小f
	c[1].num=0-b[1].num;//最大e
	for(i=1;i<=n;i++)
	{
		while((a[i]>c[et-1].num)&&et>eh)
			et--;
		c[et].num=a[i];
		c[et].book=i;
		et++;
		while((a[i]<b[ft-1].num)&&ft>fh)
			ft--;
		b[ft].num=a[i];
		b[ft].book=i;
		ft++;
        if(i>=k)
		{
			while(c[eh].book<i-k+1)
				eh++;
			while(b[fh].book<i-k+1)
				fh++;
			bb[b1]=b[fh].num;
			b1++;
			cc[c1]=c[eh].num;
			c1++;
		}
	}
	for(i=1;i<=n-k+1;i++)
		printf("%d ",bb[i]);
	printf("\n");
	for(i=1;i<=n-k+1;i++)
		printf("%d ",cc[i]);
	return 0;
}