记录编号	410741	评测结果	AAAAAAAAA
题目名称	495.[POJ 2823]滑动窗口	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.766 s
提交时间	2017-06-02 09:58:25	内存使用	15.82 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <deque>
using namespace std;

const int MAXN = 1e6 + 10;
const int INF = 0x7fffffff;

char buf[1<<18],*fs,*ft;
inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;}
inline int in(void){
    char tmp = getc();
    int res = 0, f = 1;
    while(!isdigit(tmp) && tmp ^ '-') tmp = getc();
    if(tmp == '-') f = -1, tmp = getc();
    while(isdigit(tmp))
        res = (res + (res << 2) << 1) + (tmp ^ 48),
        tmp = getc();
    return res * f;
}

struct DATA{
    int s, id;

    DATA(){;}
    DATA(int _s, int _id){
        s = _s, id = _id;
    }
};

int N, K;
deque<DATA> mx, mi;
int ans_mx[MAXN], ans_mi[MAXN];
DATA s[MAXN];
DATA tmp_1, tmp_2;

int main(){ 
#ifndef LOCAL
    freopen("window.in", "r", stdin);
    freopen("window.out", "w", stdout);
#endif
    N = in(), K = in();

    for(int i = 1; i <= N; ++i){
        s[i] = DATA(in(), i);
    }

    for(int i = 1; i <= K; ++i){
        if(mi.empty()) mi.push_back(s[i]);
        else{
           while(!mi.empty() && mi.back().s > s[i].s) mi.pop_back(); 
           mi.push_back(s[i]);
        }

        if(mx.empty()) mx.push_back(s[i]);
        else{
           while(!mx.empty() && mx.back().s < s[i].s) mx.pop_back(); 
           mx.push_back(s[i]);
        }
    }

    ans_mx[1] = mx.front().s;
    ans_mi[1] = mi.front().s;

    for(int i = 2, t = 1 + K; t <= N; ++i, ++t){
        while(mi.front().id < i && !mi.empty()) mi.pop_front();
        while(mx.front().id < i && !mx.empty()) mx.pop_front();
        if(mi.empty()) mi.push_back(s[t]);
        if(mx.empty()) mx.push_back(s[t]);
        else{
           while(!mi.empty() && mi.back().s > s[t].s) mi.pop_back(); 
           mi.push_back(s[t]);
        }

        if(mx.empty()) mx.push_back(s[t]);
        else{
           while(!mx.empty() && mx.back().s < s[t].s) mx.pop_back(); 
           mx.push_back(s[t]);
        }
        ans_mx[i] = mx.front().s;
        ans_mi[i] = mi.front().s;
    }

    for(int i = 1; i <= N - K + 1; ++i){
        printf("%d ", ans_mi[i]);
    }
    putchar('\n');
    for(int i = 1; i <= N - K + 1; ++i){
        printf("%d ", ans_mx[i]);
    }

    return 0;
}