记录编号	101375	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	OI永别	是否通过	通过
代码语言	C++	运行时间	0.543 s
提交时间	2014-05-11 19:35:19	内存使用	19.39 MiB

#include<cstdio>
#include<iostream>
using namespace std;
#define N 1000005
#define INF 0x7fffffff
int n,k;
int a[N];
int q[2][N];
int ma[N],mi[N];
inline int getint(){
	char ch = 'o';
	int x = 0;
	bool flag = 0;
	while (ch < '0' || ch > '9'){
		ch = getchar();
		if (ch == '-') break;
	}
	if (ch == '-') flag = 1,ch = getchar();
	x = ch - 48;
	while (isdigit(ch = getchar())) x = x * 10 + ch - 48;
	if (flag) x = - x;
	return x;
}

int main(){
	freopen("window.in", "r", stdin);
	freopen("window.out", "w", stdout);
	//scanf("%d %d", &n, &k);
	n = getint(); k = getint();
	for (int i = 1; i <= n; i++)
		a[i] = getint();//scanf("%d",&a[i]);
	a[0] = -INF;
	int h = 0, t = 0; q[0][0] = 0;
	for (int i = 1; i <= n; i++){
		while (h <= t && a[q[0][t]] < a[i]) t--;
		q[0][++t] = i;
		while (h < t && a[q[0][h]] < a[i] || i - q[0][h] >= k) h ++;
		if (i >= k) ma[++ma[0]] = a[q[0][h]];
	}
	a[0] = INF; h = t = 0; 
	for (int i = 1; i <= n; i++){
		while (h <= t && a[q[1][t]] > a[i]) t--;
		q[1][++t] = i;
		while (h < t && a[q[1][h]] > a[i] || i - q[1][h] >= k) h ++;
		if (i >= k) mi[++mi[0]] = a[q[1][h]];
	}
	for (int i = 1; i < mi[0]; i ++)
		printf("%d ",mi[i]);
	printf("%d\n",mi[mi[0]]);
	for (int i = 1; i < ma[0]; i ++)
		printf("%d ",ma[i]);
	printf("%d\n", ma[ma[0]]);
	
	return 0;
}