蒟蒻50分,求助

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

Round_Tree @ 2019-11-08 19:30:21

#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
using namespace std;
int n,k,a[100005],p[1000005],q[1000005],h=0,t=0;
int read(){
    char c;
    c=getchar();
    int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+(c-'0');c=getchar();}
    return x*f;
}
void quemin()
{
    int t=0,h=1;
    for(re int i=1;i<=n;i++)
    {
        while(h<=t&&q[t]>=a[i])
            t--;
        q[++t]=a[i];
        p[t]=i;
        while(p[h]<=i-k)h++;
        if(i>=k)printf("%d ",q[h]);
    }
    printf("\n");
    return ;
}
void quemax()
{
    int t=0,h=1;
    memset(p,0,sizeof(p));
    memset(q,0,sizeof(q));
    for(re int i=1;i<=n;i++)
    {
        while(h<=t&&q[t]<=a[i])
            t--;
        q[++t]=a[i];
        p[t]=i;
        while(p[h]<=i-k)h++;
        if(i>=k)printf("%d ",q[h]);
    }
    printf("\n");
    return ;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n=read();
    k=read();
    for(re int i=1;i<=n;i++)
        a[i]=read();
    quemin();
    quemax();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

by Round_Tree @ 2019-11-08 19:31:26

RE两个点

TLE一个点

WA两个点


by Plozia @ 2019-11-08 19:51:16

@呵呵哈 我只能看出RE是什么原因,剩下的我调试过,调不出来。我太蒟了

RE是因为a数组太小了,只开到10^{5},但是题目要求10^{6}(即1000000)


by Round_Tree @ 2019-11-08 21:17:12

@zzh710 十分感谢巨佬,a数组开到1000000后100了


|