80分求助

P1440 求m区间内的最小值

薇子 @ 2018-09-17 20:17:58

#include<iostream>
#include<cstdio>
using namespace std;
int a[1000005],q[1000005],num[1000005];
int fmin[1000005];
int k,n,head,tail;
void dpmin()
{
    head=1;tail=0;
    for(int i=1;i<=n;i++)
    {
        while(num[head]<i-k+1&&head<=tail) head++;
        while(a[i]<=q[tail]&&head<=tail) tail--;
        num[++tail]=i;q[tail]=a[i];
        fmin[i]=q[head];
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    printf("0\n");
    dpmin();
    for(int i=1;i<n;i++)
    printf("%d\n",fmin[i]);
    return 0;
}

by llllL_q @ 2018-09-17 20:35:58

emmm目测数组开小了(n<=2000000)


|