[已注销]!A8&kFzt @ 2019-08-26 20:04:03
评测结果
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000001];
int maxn[1000001][21],minn[1000001][21];
int rmqmin(int l,int r){
int k=log2(r-l+1);
return min(minn[l][k],minn[r-(1<<k)+1][k]);
}
int rmqmax(int l,int r){
int k=log2(r-l+1);
return max(maxn[l][k],maxn[r-(1<<k)+1][k]);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) minn[i][0]=maxn[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
minn[i][j]=min(minn[i][j-1],minn[i+(1<<j-1)][j-1]);
maxn[i][j]=max(maxn[i][j-1],maxn[i+(1<<j-1)][j-1]);
}
}
for(int i=1;i<=n-m+1;i++){
int l=i,r=l+m-1,d,p;
d=rmqmin(l,r);
printf("%d ",d);
}
printf("\n");
for(int i=1;i<=n-m+1;i++){
int l=i,r=l+m-1,d,p;
d=rmqmax(l,r);
printf("%d ",d);
}
return 0;
}
by 梧桐灯 @ 2019-08-26 20:12:53
@骨古 自己算算数组开了多大,再看看要求(好像有169mb了)
by 梧桐灯 @ 2019-08-26 20:13:01
160
by [已注销]!A8&kFzt @ 2019-08-26 20:14:01
@光随影走 哦哦3Q
by [已注销]!A8&kFzt @ 2019-08-26 20:15:42
那我还能改吗???
by 梧桐灯 @ 2019-08-26 20:20:26
@骨古 话说这道题不是RMQ哇QAQ
by [已注销]!A8&kFzt @ 2019-08-26 20:39:32
@光随影走 我知道啊,我就是想康康rmq能不能做qwq
by 梧桐灯 @ 2019-08-26 20:41:39
那会爆空间(真的)
by [已注销]!A8&kFzt @ 2019-08-26 20:59:17
@光随影走 那好吧
by ⚡小林孑⚡ @ 2019-08-26 20:59:35
@光随影走 不会吧,RMQ过的
by 梧桐灯 @ 2019-08-26 21:08:59
@脱发自动机 没有评测证据(逃)