记录编号	166140	评测结果	AAAAAAAAA
题目名称	495.[POJ 2823]滑动窗口	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.681 s
提交时间	2015-06-14 10:58:48	内存使用	23.20 MiB

/*本题借用了钢哥的神程序，结构体里写子函数，很牛；
第一个子函数：在程序一开始清空队列，让尾指针小于头指针；
第二个子函数：访问队列是否为空；
第三个子函数：返回队列首元素；
第四个子函数：将队首元素出队；
第五个子函数：返回队首元素的编号；
第六个子函数：将队尾元素出队；
第七个子函数：在队首插入元素；
第八个子函数：比较值，维护单调队列；
第九个同第八个；
连调九个子函数,幸亏钢哥是神犇，给本渣讲了很长时间才明白，本渣又打了几道题巩固一下，这才有了思路；*/
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
#define MAXN 1000001
int n,m,k;
struct dd
{
	int a[MAXN],hao[MAXN],tail,head;
	inline void qing()
	{
		head=0;
		tail=-1;
		return;
	}

	inline bool empty()
	{
		return tail<head;
	}

	inline int front()
	{
		return a[head];
	}

	inline void pop_front()
	{
		if(!empty())
		{
			head++;
		}
		return;
	}

	inline int id_id()
	{
		return  hao[head];
	}

	inline void pop_back()
	{
		tail--;
		return;
	}

	inline void push_back(int temp,int y)
	{
		 a[++tail]=temp;
		 hao[tail]=y;
		 return;
	}

	inline void push_up(int temp,int y)
	{
		while(!empty()&&a[tail]<temp)
		   pop_back();
		push_back(temp,y);
		return;
	}

	inline void push_down(int temp,int y)
	{
		while(!empty()&&a[tail]>temp)
		 pop_back();
	   push_back(temp,y);
	   return;
	}
}jie,jiege;
int za[MAXN],zb[MAXN],haha,y;
int main()
{
    freopen("window.in", "r", stdin);
	freopen("window.out", "w", stdout);

  jie.qing();
  jiege.qing();

  scanf("%d%d",&n,&k);

  for(int i=1;i<=n;++i)
  {
		scanf("%d",&y);

		jie.push_up(y,i);

		jiege.push_down(y,i);

		if(i==k)
		{
			haha++;

			za[haha]=jie.front();

			zb[haha]=jiege.front();

			continue;
		}

		if(i>k)
		{
			if(jie.id_id()==i-k)

			 jie.pop_front();

			if(jiege.id_id()==i-k)

			  jiege.pop_front();

			haha++;

			za[haha]=jie.front();

			zb[haha]=jiege.front();
		}
  }

  printf("%d",zb[1]);

  for(int i=2;i<=haha;++i)
  {
		printf(" %d",zb[i]);
  }
  printf("\n");

  printf("%d",za[1]);

  for(int i=2;i<=haha;++i)
  {
		printf(" %d",za[i]);
  }
  //system("pause");
}