记录编号	308139	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	森林	是否通过	通过
代码语言	C++	运行时间	1.142 s
提交时间	2016-09-17 08:18:58	内存使用	7.06 MiB

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<stdlib.h>
#include<string.h>
#include<functional>
#include<iomanip>
#include<math.h>
#define WJ(name) freopen(#name".in","r",stdin);freopen(#name".out","w",stdout);
#define JW fclose(stdin);fclose(stdout);
namespace mine{
	template<typename T>inline void QR(T& x){
		char ch;bool f=0;
		while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
		if(ch=='-')f=1,ch=getchar();x=ch-48;
		while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
		if(f)x=-x;
	}
	template<typename T>inline void QW(T _num){
		if(_num<0)putchar('-'),_num=-_num;
		short __cnt=0;char _str[30];
		while(_str[++__cnt]=_num%10+'0',_num/=10);
		while(putchar(_str[__cnt]),--__cnt);
	}
}
using namespace std;
using namespace mine;
const int maxn=1000000;
int a[maxn],n,k,ans[maxn];
deque<int>qmax,qmin;
inline void insert(const int& k){
	while(!qmax.empty()&&a[qmax.back()]>a[k])qmax.pop_back();qmax.push_back(k);
	while(!qmin.empty()&&a[qmin.back()]<a[k])qmin.pop_back();qmin.push_back(k);
}
int main(){
	#define submit
	#ifdef submit
	WJ(window);
	#endif
	QR(n),QR(k);
	for(int i=1;i<=n;i++)QR(a[i]);
	for(int i=1;i<k;i++)insert(i);
	for(int i=1;i<=n-k+1;i++){
		insert(i+k-1);
		while(!qmax.empty()&&qmax.front()<i)qmax.pop_front();
		while(!qmin.empty()&&qmin.front()<i)qmin.pop_front();
		QW(a[qmax.front()]),putchar(' ');
		ans[i]=a[qmin.front()];
	}
	putchar(10);
	for(int i=1;i<=n-k+1;i++)QW(ans[i]),putchar(' ');
	#ifndef submit
	system("pause");
	#endif
	JW;
	return 0;
}