记录编号	410745	评测结果	AAAAAAAAA
题目名称	[POJ 2823]滑动窗口	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.699 s
提交时间	2017-06-02 10:07:22	内存使用	4.38 MiB

# include <bits/stdc++.h>
# define MAXN 1000010
using namespace std;

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 gn() { 
    int k = 0, f = 1;
    char c = getc();
    for(; !isdigit(c); c = getc()) if(c == '-') f = -1;
    for(; isdigit(c); c = getc()) k = k * 10 + c - '0';
    return k * f;
}

struct boring_quere { 
    int wid;
    deque < pair<int, int> > q;
    inline boring_quere(){ wid = 0; }
    inline boring_quere(int l) { wid = l; }
    int mov(int pos, int k) { 
        while(!q.empty() && q.rbegin()->first >= k) q.pop_back();
        q.push_back(pair<int, int> (k, pos));
        while(q.begin()->second <= pos - wid) q.pop_front();
        return q.begin()->first;
    }
}minque, maxque;

int a[MAXN];

int main() { 
    freopen("window.in", "r", stdin);
    freopen("window.out", "w", stdout);
    int n = gn(), k = gn();
    minque.wid = k;
    maxque.wid = k;
    for(int x, i = 1; i <= n; i++) { 
        a[i] = gn();
        x = minque.mov(i, a[i]);
        if(i >= k) cout << x << " ";
    }
    cout << endl;
    for(int x, i = 1; i <= n; i++) { 
        x = 1 + ~maxque.mov(i, ~a[i] + 1);
        if(i >= k) cout << x << " "; 
    }
}