求教,为什么RE*4

P1886 滑动窗口 /【模板】单调队列

Mosklia @ 2018-06-07 11:03:25

如题,使用STL的deque实现的单调队列
可是RE\times 4
求教?

#include<cstdio>
#include<queue>
using namespace std;
template<typename comp>
struct Que{
    deque<int> elem;
    comp cmp;
    void push(int v){
        while(elem.size()){
            if(cmp(elem.back(), v))
                elem.pop_back();
            else break;
//          puts("inserting elems");
        }
        elem.push_back(v);
    }
    void pop(){
        elem.pop_front();
    }
    int front(){
        return elem.front();
    }
    bool empty(){
        return elem.empty();
    }
    int size(){
        return elem.size();
    }
};
Que<greater<int> > q1;
Que<less<int> > q2;
queue<int> ans_min, ans_max;
int a[100000+5];
int main(){
    int n, k;
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= k; ++i){
        int step;
        scanf("%d", &step);
        a[i] = step;
//      puts("Ok");
        q1.push(step);
        q2.push(step);
    }
    ans_min.push(q1.front());ans_max.push(q2.front());
    for(int i = k+1; i <= n; ++i) scanf("%d", a+i);
    for(int i = k+1; i <= n; ++i){
        if(q1.front() == a[i-k]) q1.pop();
        if(q2.front() == a[i-k]) q2.pop();
        q1.push(a[i]);q2.push(a[i]);
        ans_min.push(q1.front());
        ans_max.push(q2.front());
    }
    while(ans_min.size())
        printf("%d ", ans_min.front()),
        ans_min.pop();
    putchar('\n');
    while(ans_max.size())
        printf("%d ", ans_max.front()),
        ans_max.pop();
    return 0;
}

by AThousandSuns @ 2018-06-07 11:32:05

@Sparky_14145 注意数据范围……


by Mosklia @ 2018-06-07 13:26:32

@AThousandSuns 谢谢
写错数据范围,找了半天没找到Bug。。尴尬


|