记录编号	21461	评测结果	AAAAAAAAWA
题目名称	[POJ 2823]滑动窗口	最终得分	90
用户昵称	.Xmz	是否通过	未通过
代码语言	C++	运行时间	2.581 s
提交时间	2010-11-10 22:08:14	内存使用	10.53 MiB

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

using namespace std;

int n,k;
int a[1000001];
struct queue
{
	int x[1000001];
	int id[1000001];
	int qt,qw;
	
	void add(int v,int idd)
	{
		while (qw>=qt && v<x[qw]) qw--;
		x[++qw]=v;
		id[qw]=idd;
	}
	int get(int idd)
	{
		while (qt<=qw && id[qt]<=idd) qt++;
		return x[qt];
	}
}q;
int qt,qw;
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);
	q.qt=1;q.qw=0;
	for (int i=1;i<=k-1;i++)
	q.add(a[i],i);
	for (int i=k;i<=n;i++)
	{
		q.add(a[i],i);
		if (i!=n) printf("%d ",q.get(i-k));
		else printf("%d\n",q.get(i-k));
	}
	for (int i=1;i<=n;i++)
	a[i]=-a[i];
	q.qt=1;q.qw=0;
	for (int i=1;i<=k-1;i++)
	q.add(a[i],i);
	for (int i=k;i<=n;i++)
	{
		q.add(a[i],i);
		if (i!=n) printf("%d ",-q.get(i-k));
		else printf("%d\n",-q.get(i-k));
	}
	return 0;
}