记录编号	453946	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	Hyoi_0Koto	是否通过	通过
代码语言	C++	运行时间	0.948 s
提交时间	2017-09-27 22:09:01	内存使用	29.97 MiB

/*written by 0koto*/
#prag\
ma GCC optimize("O3")
#include<cstdio>
#include<cctype>
#include<deque>
#include<vector>
#define loop(i,j,k) for(int i=j;i<=k;++i)
#define smax(a,b) a>b?a:b
#define smin(a,b) a<b?a:b
using namespace std;
inline void in(int &x){
    x=0;int f=1;char c=getchar();
    while(!isdigit(c)){if(!(c-'-'))f=-1;c=getchar();}
    while (isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
    x*=f;
}
inline void out(int x){
    if(!x){putchar('0');return;}
    if(x<0)x=~x+1,putchar('-');
    char c[30]={0};
    while(x)c[++c[0]]=x%10+48,x/=10;
    while(c[0])putchar(c[c[0]--]);
}
const int maxn=10e6+1;
int n,k,a[maxn];
deque<int> qmax,qmin;
vector<int> amax,amin;
inline void max_push(int x,int p){
	if(qmax.empty()){
		qmax.push_back(p);return;
	}
	while((!qmax.empty())&&a[qmax.back()]<x) qmax.pop_back();
	qmax.push_back(p);
}
inline void min_push(int x,int p){
	if(qmin.empty()){
		qmin.push_back(p);return;
	}
	while((!qmin.empty())&&a[qmin.back()]>x) qmin.pop_back();
	qmin.push_back(p);
}
inline void max_pop(int p){
	if(!qmax.empty()){
		while(qmax.front()<p) qmax.pop_front();
	}
}
inline void min_pop(int p){
	if(!qmin.empty()){
		while(qmin.front()<p) qmin.pop_front();
	}
}
inline void ans_max(){
	amax.push_back(a[qmax.front()]);
}
inline void ans_min(){
	amin.push_back(a[qmin.front()]);
}
inline int koto(){
	freopen("window.in","r",stdin);
	freopen("window.out","w",stdout);
	in(n),in(k);
	loop(i,1,k) in(a[i]),max_push(a[i],i),min_push(a[i],i);
	ans_max(),ans_min();
	loop(i,k+1,n) in(a[i]),max_push(a[i],i),min_push(a[i],i),max_pop(i-k+1),min_pop(i-k+1),ans_max(),ans_min();
	for(int i=0;i<amin.size();++i)out(amin[i]),putchar(' ');putchar('\n');
	for(int i=0;i<amax.size();++i)out(amax[i]),putchar(' ');putchar('\n');
}
int zero=koto();
int main(){;}