Dream_weavers @ 2022-01-13 19:16:55
rt，数组开小RE，数组开大MLE，出题人不能把空间限制开大点么？良心呢？
丧心病狂的提交记录
上code：
#include<iostream>
#include<cstdio>
#include<cmath>
#define N 1000001
using namespace std;
typedef long long ll;
ll n,a[N],i,j,stma[N][18],stmi[N][18],Q,l,r,kk,k;
int main(){
ios::sync_with_stdio(0);
scanf("%lld%lld",&n,&kk);
for(i=1;i<=n;i++) {
scanf("%lld",a+i);
stma[i][0]=stmi[i][0]=a[i];;
}
for(j=1;(1<<j)<=n;j++){
for(i=1;(i+(1<<j)-1)<=n;i++){
stma[i][j]=max(stma[i][j-1],stma[i+(1<<(j-1))][j-1]);
stmi[i][j]=min(stmi[i][j-1],stmi[i+(1<<(j-1))][j-1]);
}
}
for(l=1,r=kk;r<=n;l++,r++){
k=log2(r-l+1);
cout<<min(stmi[l][k],stmi[r-(1<<k)+1][k])<<" ";
}cout<<'\n';
for(l=1,r=kk;r<=n;l++,r++){
k=log2(r-l+1);
cout<<max(stma[l][k],stma[r-(1<<k)+1][k])<<" ";
}
return 0;
}by int233 @ 2022-01-13 19:20:57
@Dream_weavers 你不能开两个数组，开一个数组，先算最大再算最小就行了。
by int233 @ 2022-01-13 19:21:24
亲测可用
by int233 @ 2022-01-13 19:25:07
我的代码：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
int st[1000005][21];
int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int que(int l,int r){
int k=log2(r-l+1);
return max(st[l][k],st[r-(1<<k)+1][k]);
}
int que_stm(int l,int r){
int k=log2(r-l+1);
return min(st[l][k],st[r-(1<<k)+1][k]);
}
int main(){
int n,k,l,r;
n=read();k=read();
for(int i=1;i<=n;i++){
st[i][0]=read();
}
for(int i=1;(1<<i)<=n;i++){
for(int j=1;j+(1<<i)-1<=n;j++){
st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
}
for(int i=1;i<=n-k+1;i++){
cout<<que_stm(i,i+k-1)<<" ";
}
cout<<endl;
for(int i=1;(1<<i)<=n;i++){
for(int j=1;j+(1<<i)-1<=n;j++){
st[j][i]=1e9;
}
}
for(int i=1;(1<<i)<=n;i++){
for(int j=1;j+(1<<i)-1<=n;j++){
st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
}
for(int i=1;i<=n-k+1;i++){
cout<<que(i,i+k-1)<<" ";
}
return 0;
} by int233 @ 2022-01-13 19:25:56
出题人要卡你这个程序。
by Dream_weavers @ 2022-01-13 19:29:23
@卫道士qwq 我操，我把long long改成int就对了！