萌新第一次写单调队列 和题解做法一样 为什么只有30分

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

Bianca_ @ 2018-07-19 20:35:19

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,k;
int head=1,tail=1;
struct node{
    int num,tag;
};
node a[1000010],q[1000010];
inline void pop_front(){
    head++;
    return;
}
inline void pop_back(){
    tail--;
    return;
}
inline void push(node x){
    q[tail].num=x.num;
    q[tail].tag=x.tag;
    tail++;
    return;
}
inline bool q_empty(){
    return head==tail;
} 
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i].num);
        a[i].tag=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=tail-1;j>=1;j--) if(!q_empty()&&q[j].num>=a[i].num) pop_back();
        push(a[i]);
        while(q[head].tag<=a[i].tag-k) pop_front();
        if(i>=k) printf("%d ",q[head].num);
    }
    printf("\n");
    head=1,tail=1;
    for(int i=1;i<=n;i++) q[i].num=0,q[i].tag=0;
    for(int i=1;i<=n;i++){
        for(int j=tail-1;j>=1;j--) if(!q_empty()&&q[j].num<=a[i].num) pop_back();
        push(a[i]);
        while(q[head].tag<=a[i].tag-k) pop_front();
        if(i>=k) printf("%d ",q[head].num);
    }
    return 0;
}

by Bianca_ @ 2018-07-19 20:38:45

而且诡异的是T了第二个点 然而下了数据之后 答案秒出???


|