记录编号	239247	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	1.007 s
提交时间	2016-03-20 09:14:51	内存使用	7.05 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
template<typename T>
struct deque{
private:
	static const int maxn=1010;
	T a[maxn];
	int head,tail;
public:
	deque(){
		memset(a,0,sizeof(a));
		head=tail=0;
	}
	void clear(){
		deque();
	}
	int size(){
		return head>tail?tail-head+maxn:tail-head;
	}
	bool empty(){
		return head==tail;
	}
	void push_back(const T& n){
		a[tail++]=n;
		if(tail==maxn) tail=0;
	}
	T pop_front(){
		T n=a[head++];
		if(head==maxn)head=0;
		return n;
	}
	void push_front(const T& n){
		if(head==0)head=maxn+1;
		a[--head]=n;
	}
	T pop_back(){
		if(tail==0)tail=maxn+1;
		T n=a[--tail];
		return n;
	}
	T& front(){
		return a[head];
	}
	T& back(){
		if(tail==0)
		return a[tail-1];
	}
	T& end(){
		return a[tail-1];
	}
	bool in(const int &n){
		for(int i=0;i<size();i++)if(a[head+i>=maxn?head+n-maxn:head+n]==n)return true;
		return false;
	}
	T& operator[](const int& n){
		if(head+n>=maxn)return a[head+n-maxn];
		return a[head+n];
	}
};
struct abc{
	int data,num;
	abc(int a=0,int b=0):data(a),num(b){}
};
deque<abc> qmx,qmn;
int n,k;
int mx[1000010],mn[1000010];
int main(){
#define COGS
#ifdef COGS
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
#endif
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		int num;
		scanf("%d",&num);
		if(qmx.empty())qmx.push_back(abc(num,i));
		else{
			while(!qmx.empty()&&qmx.end().data<num)qmx.pop_back();
			qmx.push_back(abc(num,i));
			if(qmx.front().num==i-k)qmx.pop_front();
		}
		if(qmn.empty())qmn.push_back(abc(num,i));
		else{
			while(!qmn.empty()&&qmn.end().data>num)qmn.pop_back();
			qmn.push_back(abc(num,i));
			if(qmn.front().num==i-k)qmn.pop_front();
		}
		if(i>=k){
			mx[i]=qmn.front().data;
			mn[i]=qmx.front().data;
		}
	}
	for(int i=k;i<=n;i++)printf("%d ",mx[i]);
	putchar('\n');
	for(int i=k;i<=n;i++)printf("%d ",mn[i]);
	return 0;
}