高能一号 @ 2017-07-21 14:09:16
RT,怎么调都要T一个点
#include<stdio.h>
#include<cmath>
#define N 1000005
#define M 40001
#define oo 2147483647
#define For(i,j,k) for(int i=j;i<=k;++i)
using namespace std;
int read(){
int l=1,x=0; char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') ch=getchar(),l=-1;
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*l;
}
int a[N],bel[N],blockmax[M],blockmin[M],bl[M],br[M],maxn[N];
int main(){
int n=read(),m=read(),ma,mi,l,r,sqn,sum;
sqn=pow(n,2.0/8.3); sum=n/sqn; if (sum%sqn) sum++; //printf("%d ",sqn);
For(i,1,n) a[i]=read();
For(i,1,sum-1){
bl[i]=(i-1)*sqn+1; br[i]=i*sqn;
ma=-oo; mi=oo;
For(j,bl[i],br[i]) {
bel[j]=i;
if (a[j]>=ma) ma=a[j];
if (a[j]<=mi) mi=a[j];
}
blockmax[i]=ma; blockmin[i]=mi;
}
bl[sum]=br[sum-1]+1; br[sum]=n;
ma=-oo; mi=oo;
For(j,bl[sum],br[sum]){
bel[j]=sum;
if (a[j]>=ma) ma=a[j];
if (a[j]<=mi) mi=a[j];
}
blockmax[sum]=ma; blockmin[sum]=mi;
For(i,1,n-m+1){
l=i; r=i+m-1;
ma=-oo; mi=oo;
if (bel[l]==bel[r])
For(j,l,r){
if (a[j]>=ma) ma=a[j];
if (a[j]<=mi) mi=a[j];
}
else{
For(j,l,br[bel[l]]){
if (a[j]>=ma) ma=a[j];
if (a[j]<=mi) mi=a[j];
}
For(j,bel[l]+1,bel[r]-1){
if (ma<=blockmax[j]) ma=blockmax[j];
if (mi>=blockmin[j]) mi=blockmin[j];
}
For(j,bl[bel[r]],r){
if (a[j]>=ma) ma=a[j];
if (a[j]<=mi) mi=a[j];
}
}
printf("%d ",mi); maxn[i]=ma;
}
printf("\n");
For(i,1,n-m+1) printf("%d ",maxn[i]);
return 0;
}
@远航之曲
by 1124828077ccj @ 2017-07-21 17:51:52
@高能一号 这题正解是单调队列。。。分块你算算时间复杂度。。。
by 高能一号 @ 2017-07-22 14:47:24
@2016陈常杰 可是我只T了一个啊
by 1124828077ccj @ 2017-07-22 20:32:29
@高能一号 这题数据真的很弱,我当时爆搜加了个优化就过了。。。