记录编号	36798	评测结果	AAAAAAAAA
题目名称	495.[POJ 2823]滑动窗口	最终得分	100
用户昵称	kaaala	是否通过	通过
代码语言	C++	运行时间	1.931 s
提交时间	2012-03-19 21:01:52	内存使用	4.08 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<deque>

using namespace std;

int N,K,A[1000010];
deque<int>deq;

int main()
{
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
	scanf("%d%d",&N,&K);
	for(int i=1;i<=N;i++)
		scanf("%d",&A[i]);
	for(int i=1;i<=N;i++)
	{
		while(!deq.empty()&&A[i]<=A[deq.back()])
			deq.pop_back();
		deq.push_back(i);
		if(i-deq.front()>=K)
			deq.pop_front();
		if(i>=K)
			printf("%d ",A[deq.front()]);
	}
	printf("\n");
	deq.clear();
	for(int i=1;i<=N;i++)
	{
		while(!deq.empty()&&A[i]>=A[deq.back()])
			deq.pop_back();
		deq.push_back(i);
		if(i-deq.front()>=K)
			deq.pop_front();
		if(i>=K)
			printf("%d ",A[deq.front()]);
	}
	printf("\n");
	return 0;
}