st表MLE 70求助

QZY2008 @ 2021-09-16 22:33:41

by QZY2008 @ 2021-09-16 22:34:04

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+5;
const ll M=20;
ll lg[N];
ll num[N];
ll st[N][M+5];
int main(){
    ll n,k;
    scanf("%lld%lld",&n,&k);
    lg[0]=-1;
    for (ll i=1;i<=n;i++)
        scanf("%lld",&num[i]),st[i][0]=num[i],lg[i]=lg[i>>1]+1;
    for (ll j=1;j<=M;j++)
        for (ll i=1;i+(1<<j)-1<=n;i++)
            st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
    for (ll i=1;i<=n-k+1;i++){
        ll l=i,r=i+k-1,d=lg[r-l+1];
        printf("%lld ",min(st[l][d],st[r-(1<<d)+1][d]));
    }
    putchar('\n');
    for (ll i=1;i<=n;i++)
        st[i][0]=num[i],lg[i]=lg[i>>1]+1;
    for (ll j=1;j<=M;j++)
        for (ll i=1;i+(1<<j)-1<=n;i++) 
            st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
    for (ll i=1;i<=n-k+1;i++){
        ll l=i,r=i+k-1,d=lg[r-l+1];
        printf("%lld ",max(st[l][d],st[r-(1<<d)+1][d]));
    }
}

by Terrible @ 2021-09-16 22:47:36

空间不够，很多空间储存的都是冗余的东西。

不要什么都用long long

by QZY2008 @ 2021-09-16 22:49:11

@Terrible 谢谢

by QZY2008 @ 2021-09-16 22:51:23

@Terrible 已过，谢谢