记录编号	166502	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.770 s
提交时间	2015-06-15 14:45:15	内存使用	23.21 MiB

#include<deque>
#include<vector>
#include<iostream>
#include<fstream>

using namespace std;
struct node
{
	int id, val;
};
typedef vector<int> vi;

const int MAXN = 3000001;
node w[MAXN];
vi minn, maxx;
int n, k;
deque<node> mi, ma;
ifstream fi("window.in");
ofstream fo("window.out");
#define cin fi
#define cout fo

main()
{
//	ios::sync_with_stdio(false);
	cin >> n >> k;
	for(int i = 1; i <= n; i ++)
	{
		cin >> w[i].val;
		
		w[i].id = i;
	}	
	for(int i = 1; i <= k; i ++)
	{
		if(mi.empty())
			mi.push_back(w[i]);
		else
		{
			while(! mi.empty())
			{
				if(mi.back().val > w[i].val)
				{
					mi.pop_back();
					continue;
				}
				break;
			}
			mi.push_back(w[i]);
		}
		if(ma.empty())
			ma.push_back(w[i]);
		else
		{
			while(! ma.empty())
			{
				if(ma.back().val < w[i].val)
				{
					ma.pop_back();
					continue;
				}
				break;
			}
			ma.push_back(w[i]);
		}
	}
	int tail = 1;
	minn.push_back(mi.front().val);
	maxx.push_back(ma.front().val);
	for(int i = k + 1; i <= n; i ++)
	{
		tail ++;
		while(mi.front().id < tail && ! mi.empty())
			mi.pop_front();
		while(ma.front().id < tail && ! ma.empty())
			ma.pop_front();
		if(mi.empty())
			mi.push_back(w[i]);
		else
		{
			while(! mi.empty())
			{
				if(mi.back().val > w[i].val)
				{
					mi.pop_back();
					continue;
				}
				break;
			}
			mi.push_back(w[i]);
		}
		if(ma.empty())
			ma.push_back(w[i]);
		else
		{
			while(! ma.empty())
			{
				if(ma.back().val<w[i].val)
				{
					ma.pop_back();
					continue;
				}
				break;
			}
			ma.push_back(w[i]);
		}
		minn.push_back(mi.front().val);
		maxx.push_back(ma.front().val);
	}
	
	for(vi::iterator it = minn.begin(); it != minn.end(); ++ it)
	{
		cout << *it;
		if(it != minn.end() - 1)
			cout << ' ';
		else
			cout << endl;
	}
	for(vi::iterator it = maxx.begin(); it != maxx.end(); ++ it)
	{
		cout << *it;
		if(it != maxx.end() - 1)
			cout << ' ';
	}
}