记录编号	166507	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	啊啦吧啦吧啦	是否通过	通过
代码语言	C++	运行时间	0.770 s
提交时间	2015-06-15 14:49:49	内存使用	19.39 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1000001;
int n,k;
int a[maxn],b[maxn],c[maxn];
int ma[maxn],mi[maxn];
int hmax=1,tmax=0,hmin=1,tmin=0;
void insertmax(int x)
{
	while(hmax<=tmax && a[x]>=a[b[tmax]]) tmax--;
	
	tmax++;
	b[tmax]=x;
}
void insertmin(int x)
{
	while(hmin<=tmin && a[x]<=a[c[tmin]]) tmin--;
	
	tmin++;
	c[tmin]=x;
}
int main()
{
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
 	ios::sync_with_stdio(false);
	cin>>n>>k;
	if(k>n) k=n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=k-1;i++)
	{
		insertmax(i);
		insertmin(i);
	}
	for(int i=k;i<=n;i++)
	{
		insertmax(i);
		insertmin(i);
		if(b[hmax]<i-k+1) hmax++;
		if(c[hmin]<i-k+1) hmin++;
		ma[i-k+1]=a[b[hmax]];
		mi[i-k+1]=a[c[hmin]];
	}
	for(int i=1;i<=n-k;i++)
		cout<<mi[i]<<' ';
	cout<<mi[n-k+1]<<endl;
	
	for(int i=1;i<=n-k;i++)
		cout<<ma[i]<<' ';
	cout<<ma[n-k+1];
//	system("pause");
//	fclose(stdin);
//	fclose(stdout);
 	return 0;
}