记录编号	21469	评测结果	AAAAAAAAA
题目名称	495.[POJ 2823]滑动窗口	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	1.648 s
提交时间	2010-11-11 07:09:32	内存使用	4.08 MiB

/*
ID: dxmtb
PROG: poj2823 Sliding Window
TIME: 2010.6.3
STATE: Solved
MEMO: dp 单调队列
*/
#include <cstdio>
#include <deque>
#include <cstring>
using namespace std;

const int MAXN=1000005;

int n,k;
int a[MAXN];

inline void put(int x){
	if(x< 0){
		putchar('-');
		x = -x;
	}
	if(x == 0){
		putchar('0');
		return;
	}
	char s[20];
	int bas = 0;
	for(;x;x/=10)s[bas++] = x%10+'0';
	for(;bas--;)putchar(s[bas]);
	return;
}


int main()
{
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
	scanf("%d%d\n",&n,&k);
	for(int i=0;i<n;i++)
		scanf("%d",a+i);
	deque<int> q;
	for(int i=0;i<n;i++)
	{
		while (!q.empty()&&a[i]<=a[q.back()])
			q.pop_back();
		q.push_back(i);
		if(i-q.front()>=k)
			q.pop_front();
		if (i>=k)
			putchar(' ');
		if (i>=k-1)
			put(a[q.front()]);
	}
	putchar('\n');
	q.clear();
	for(int i=0;i<n;i++)
	{
		while (!q.empty()&&a[i]>=a[q.back()])
			q.pop_back();
		q.push_back(i);
		if(i-q.front()>=k)
			q.pop_front();
		if (i>=k)
			putchar(' ');
		if (i>=k-1)
			put(a[q.front()]);
	}	
	return 0;
}