记录编号	442631	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.802 s
提交时间	2017-08-27 21:44:41	内存使用	19.39 MiB

#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000005],head=1,tail,h=1,t;
struct h{
	int cost,seat;
}ma[1000005],mi[1000005];
int main()
{
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	memset(mi,-0x3f,sizeof(mi));
	for(int i=1;i<=n;i++){
		while(a[i]<=mi[tail].cost)
		tail--;
		mi[++tail].cost=a[i];
		mi[tail].seat=i;
		if(i-mi[head].seat+1>k){
			mi[head].cost=-0x7fffffff;
			head++;
		}
		if(i>=k)
		cout<<mi[head].cost<<" ";
	}
	cout<<endl;
	memset(ma,0x3f,sizeof(ma));
	for(int i=1;i<=n;i++){
		while(a[i]>=ma[t].cost)
		t--;
		ma[++t].cost=a[i];
		ma[t].seat=i;
		if(i-ma[h].seat+1>k){
			ma[h].cost=0x7fffffff;
			h++;
		}
		if(i>=k)
		cout<<ma[h].cost<<" ";
	}
	return 0;
}