记录编号	129764	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.814 s
提交时间	2014-10-20 21:18:07	内存使用	17.23 MiB

#include<iostream>
#include<cstdio>
using namespace std;
int h_max=1,t_max=0,h_min=1,t_min=0;
int a[1000001],b[1000001],c[1000001];
int ma[1000001],mi[1000001];
void insert_max(int x);
void insert_min(int x);
int n,k;
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++)
	{
		insert_max(i);
		insert_min(i);
	}
	for(int i=k;i<=n;i++)
	{
		insert_max(i);
		insert_min(i);
		if(b[h_max]<i-k+1) h_max++;
		if(c[h_min]<i-k+1) h_min++;
		ma[i-k+1]=a[b[h_max]];
		mi[i-k+1]=a[c[h_min]];
	}
	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];
	return 0;
}
void insert_max(int x)
{
	while(h_max<=t_max && a[x]>=a[b[t_max]]) t_max--;
	t_max++;b[t_max]=x;
}
void insert_min(int x)
{
	while(h_min<=t_min && a[x]<=a[c[t_min]]) t_min--;
	t_min++;c[t_min]=x;
}