记录编号	165859	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.534 s
提交时间	2015-06-13 09:12:40	内存使用	20.60 MiB

//AUTHOR::STDAFX
//ALGORITHM::DEQUE
 
#define MAXN 1000010UL
 
#include <cstdio>
 
using namespace std;
 
struct Deq{
    int data[MAXN],tail,head,id[MAXN];
    inline void clr(){
        tail=-1;
        head=0;
        return;
    }
    inline bool empty(){
        return tail<head;
    }
    inline void pop_front(){
        if(!empty()){
            head++;
        }
        return;
    }
    inline void push_back(int temp,int new_id){
        data[++tail]=temp;
        id[tail]=new_id;
        return;
    }
    inline void pop_back(){
        tail--;
        return;
    }
    inline int front(){
        return data[head];
    }
    inline int front_id(){
        return id[head];
    }  
    inline int back(){
        return data[tail];
    }
    inline void push_up(int temp,int new_id){
        while(!empty()&&back()>temp){
            pop_back();
        }
        push_back(temp,new_id);
        return;
    }
    inline void push_down(int temp,int new_id){
        while(!empty()&&back()<temp){
            pop_back();
        }
        push_back(temp,new_id);
        return;
    }
};
 
Deq deq_max,deq_min;
 
int Max[MAXN],Min[MAXN],n,length,temp,cs;
 
inline int in();
 
int main(){
    freopen("window.in","r",stdin);
    freopen("window.out","w",stdout);
    n=in();length=in();
    deq_max.clr();deq_min.clr();
    for(int i=1;i<=n;i++){
        temp=in();
        deq_max.push_down(temp,i);
        deq_min.push_up(temp,i);
        if(i==length){
            cs++;
            Max[cs]=deq_max.front();
            Min[cs]=deq_min.front();
            continue;
        }
        if(i>length){
            if(deq_max.front_id()==i-length){
                deq_max.pop_front();
            }
            if(deq_min.front_id()==i-length){
                deq_min.pop_front();
            }          
            cs++;
            Max[cs]=deq_max.front();
            Min[cs]=deq_min.front();   
        }
    }
    printf("%d",Min[1]);
    for(int i=2;i<=cs;i++){
        printf(" %d",Min[i]);
    }
    printf("\n");
    printf("%d",Max[1]);
    for(int i=2;i<=cs;i++){
        printf(" %d",Max[i]);
    }  
    //fclose(stdin);
    //fclose(stdout);  
    return 0;
}
 
inline int in(){
    int temp=0;bool flag=0;char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') flag=1;
        c=getchar();
    }
    for(;c>='0'&&c<='9';c=getchar()){
        temp=temp*10+c-48;
    }
    if(flag) return -temp;
    return temp;
}
 
/**************************************************************
    Problem: 22030
    User: hznq60082
    Language: C++
    Result: 正确
    Time:409 ms
    Memory:24528 kb
****************************************************************/