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

# include <bits/stdc++.h>
# define MAXN 1000010
using namespace std;
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, k;
    cin >> n >> k;
    minque.wid = k;
    maxque.wid = k;
    for(int x, i = 1; i <= n; i++) { 
        cin >> a[i];
        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 << " "; 
    }
}