记录编号	464632	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	Regnig Etalsnart	是否通过	通过
代码语言	C++	运行时间	0.719 s
提交时间	2017-10-25 21:35:43	内存使用	18.03 MiB

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1000001;
int n,k,minn[maxn],maxx[maxn],i;
int head=1,tail=0;
struct DSC{int num,at;}a[maxn],q[maxn];
bool empty(){return tail<head;}
void push(DSC x){q[++tail]=x;return;}
void popf(){head++;}
void popb(){q[tail].num=0;q[tail].at=0;tail--;}
void clear(){while(tail)popb();}
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].num);
		a[i].at=i;
	}
	push(a[1]);
	for(i=2;i<=n;i++)
	{
		if(i-q[head].at==k)popf();
		if(a[i].num>q[tail].num)push(a[i]);
		else
		{
			while(a[i].num<=q[tail].num&&empty()==0)popb();
			push(a[i]);
		}
		minn[i]=q[head].num;
	}
	clear();
	head=1;tail=0;
	push(a[1]);
	for(i=2;i<=n;i++)
	{
		if(i-q[head].at==k)popf();
		if(a[i].num<q[tail].num)push(a[i]);
		else
		{
			while(a[i].num>=q[tail].num&&empty()==0)popb();
			push(a[i]);
		}
		maxx[i]=q[head].num;
	}
	for(i=k;i<=n;i++)printf("%d ",minn[i]);printf("\n");
	for(i=k;i<=n;i++)printf("%d ",maxx[i]);printf("\n");
	return 0;
}
int main(){;}
int syy=Main();