huangwux @ 2019-10-25 22:56:15
#include<iostream>
#include<string>
#include<queue>
#include<cstdio>
#include<string.h>
using namespace std;
int n,m;
int a[1000100];
int maxx[1000010],minx[1000010];
int now_max,now_min;
int q_max[1000010],q_min[1000010];
int main(){
//freopen("4.in","r",stdin);
memset(maxx,-0x3f3f3f3f,sizeof(maxx));
memset(minx,0x3f3f3f3f,sizeof(minx));
//q_max[1]=-0x3f,q_min[1]=0x3f;
scanf("%d%d",&n,&m);
//int k=m;
//cout<<n<<" "<<m<<endl;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),maxx[i]=minx[i]=a[i];
/*for(int i=1;i<=n;i++)
printf("%d %d\n",maxx[i],minx[i]);
for(int i=1;i<=m;i++)
{
if(a[i]>=maxx[m])
maxx[m]=a[i],q_max[1]=i;
if(a[i]<=minx[m])
minx[m]=a[i],q_min[1]=i;
}
printf("%d %d %d %d\n",maxx[m],minx[m],q_max[1],q_min[1]);*/
//maxx[m]=q_max[1],minx[m]=q_min[1];
int l1=1,r1=1,l2=1,r2=1;
q_max[1]=q_min[1]=1;
for(int i=1;i<=n;i++){
while(l1<=r1&&i-q_max[l1]>=m) l1++;
maxx[i]=max(maxx[i],a[q_max[l1]]);
//printf("%d ",maxx[i]);
while(l1<=r1&&a[q_max[r1]]<=a[i]) r1--;
q_max[++r1]=i;
while(l2<=r2&&i-q_min[l2]>=m) l2++;
minx[i]=min(minx[i],a[q_min[l2]]);
while(l2<=r2&&a[q_min[r2]]>=a[i]) r2--;
q_min[++r2]=i;
}
for(int i=m;i<=n;i++)
{
printf("%d ",minx[i]);
}
puts(" ");
for(int i=m;i<=n;i++)
{
printf("%d ",maxx[i]);
}
}
by 梧桐灯 @ 2019-10-25 22:59:03
哪有这样memset的……
by nth_element @ 2019-10-25 23:09:25
memset(maxx,-0x3f3f3f3f,sizeof(maxx));
这时maxx[]
是正数
by nth_element @ 2019-10-25 23:09:31
@huangwux