这题数据有毒

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

Anakin @ 2018-10-02 22:43:30

第一个数据下载了之后本地评测能过,提交就wa了,求大佬帮看

#include<iostream>
#include<cstring>
#include<cstdio>
#define MAXN 1000000+10
using namespace std;
inline int read(){
    int out=0,f=1;
    char c=getchar();
    if(c==45) f=-1;
    while(c<48||c>57) c=getchar();
    while(c<=57&&c>=48){
        out=(out<<1)+(out<<3)+c-48;
        c=getchar();
    }
    return out*f;
}
void write(int x){
    if(x<0){
        putchar(45);
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+48);
}
int qmax[MAXN],pmax[MAXN];
int qmin[MAXN],pmin[MAXN];
int a[MAXN];
int n,m;
int main(){
    n=read();
    m=read();
    int head1=1,head2=1;
    int tail2=0,tail1=0;
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<=n;++i){
        int x=a[i];
        while(head2<=tail2&&qmin[tail2]>=x) --tail2;
        qmin[++tail2]=x;
        pmin[tail2]=i;
        while(pmin[head2]<=i-m) ++head2;
        if(i>=m){
            write(qmin[head2]);
            putchar(32);
        }
    }
    putchar(10);
    for(int i=1;i<=n;++i){
        int x=a[i];
        while(head1<=tail1&&qmax[tail1]<=x) --tail1;
        qmax[++tail1]=x;
        pmax[tail1]=i;
        while(pmax[head1]<=i-m) ++head1;
        if(i>=m){
            write(qmax[head1]);
            putchar(32);
        }
    }   
    return 0;
}

by WA鸭鸭 @ 2018-10-02 22:55:30

@Anakin 在洛谷IDE测


by AThousandSuns @ 2018-10-02 22:56:55

@Anakin 您read写炸了……注意一下f……


by 权御天下 @ 2018-10-02 23:00:15

我可以来安利我博客里的快读模板吗


by IRipple @ 2018-10-03 00:26:30

@Anakin 我试过了,把快读改成cin就AC了,可能是你快读写挫了(来自不用快读的蒟蒻)


by Anakin @ 2018-10-03 11:02:47

@恣扬_Elite 我试试,感谢


by Anakin @ 2018-10-03 11:06:09

@恣扬_Elite 改成scanf过了。。。。


|