记录编号	306975	评测结果	WWAWAAWWW
题目名称	[POJ 2823]滑动窗口	最终得分	33
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	1.354 s
提交时间	2016-09-13 16:14:52	内存使用	7.06 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<deque>
using namespace std;
const int maxn=1000010;
template<typename T,class compare=less<T>,class base=std::deque<pair<T,int> > >
struct boring_queue{
	base q;
	int cnt;
	compare cmp;
	boring_queue():q(base()),cnt(0),cmp(compare()){}
	void clear(){
		*this=base();
		cnt=0;
	}
	void push(const T &x){
		while(!q.empty()&&cmp(x,q.back().first))q.pop_back();
		q.push_back(make_pair(x,++cnt));
	}
	void refresh(int x){
		while(!q.empty()&&q.front().second<=x)q.pop_front();
	}
	bool empty()const{
		return q.empty();
	}
	T &front(){
		return q.front().first;
	}
	T &back(){
		return q.back().first;
	}
};//默认维护一个单调增的单调队列
boring_queue<int>qmin;
boring_queue<int,greater<int> >qmax;
int n,m,x,a[maxn],b[maxn];
int main(){
#define MINE
#ifdef MINE
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
#endif
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		qmin.push(x);
		qmax.push(x);
		if(i>=m){
			a[i]=qmin.front();
			b[i]=qmax.front();
		}
		qmin.refresh(i-m);
		qmax.refresh(i-m);
	}
	for(int i=m;i<=n;i++)printf("%d ",a[i]);
	printf("\n");
	for(int i=m;i<=n;i++)printf("%d ",b[i]);
#ifndef MINE
	printf("\n--------------------DONE--------------------\n");
	for(;;);
#endif
	return 0;
}