RE经历了什么,求助

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

吴耀坤 @ 2019-06-07 15:15:02

#include<cstdio>
#include<deque>
#define MP make_pair

using namespace std;
deque<pair<int ,int> >q;
int n,a[200000],w;
int main()
{
    scanf("%d%d",&n,&w);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    for(int i=1;i<=n;i++)
    {
        while(!q.empty()&&i-q.front().first>=w) q.pop_front();
        while(!q.empty()&&q.back().second>=a[i]) q.pop_back();
        q.push_back(MP(i,a[i]));
        if(i>=w) printf("%d ",q.front().second);
    }
    printf("\n");
    q.clear();
        for(int i=1;i<=n;i++)
    {
        while(!q.empty()&&i-q.front().first>=w) q.pop_front();
        while(!q.empty()&&q.back().second<=a[i]) q.pop_back();
        q.push_back(MP(i,a[i]));
        if(i>=w) printf("%d ",q.front().second);
    }
}

by presucc @ 2019-06-07 15:18:18

@吴耀坤 数据范围 10^6,您的数组只有2*10^5


by 吴耀坤 @ 2019-06-16 15:04:57

@LZCR 非常感谢


|