Round_Tree @ 2019-11-08 19:30:21
#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
using namespace std;
int n,k,a[100005],p[1000005],q[1000005],h=0,t=0;
int read(){
char c;
c=getchar();
int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+(c-'0');c=getchar();}
return x*f;
}
void quemin()
{
int t=0,h=1;
for(re int i=1;i<=n;i++)
{
while(h<=t&&q[t]>=a[i])
t--;
q[++t]=a[i];
p[t]=i;
while(p[h]<=i-k)h++;
if(i>=k)printf("%d ",q[h]);
}
printf("\n");
return ;
}
void quemax()
{
int t=0,h=1;
memset(p,0,sizeof(p));
memset(q,0,sizeof(q));
for(re int i=1;i<=n;i++)
{
while(h<=t&&q[t]<=a[i])
t--;
q[++t]=a[i];
p[t]=i;
while(p[h]<=i-k)h++;
if(i>=k)printf("%d ",q[h]);
}
printf("\n");
return ;
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
n=read();
k=read();
for(re int i=1;i<=n;i++)
a[i]=read();
quemin();
quemax();
fclose(stdin);
fclose(stdout);
return 0;
}
by Round_Tree @ 2019-11-08 19:31:26
RE两个点
TLE一个点
WA两个点
by Plozia @ 2019-11-08 19:51:16
@呵呵哈 我只能看出RE是什么原因,剩下的我调试过,调不出来。我太蒟了
RE是因为a数组太小了,只开到
by Round_Tree @ 2019-11-08 21:17:12
@zzh710 十分感谢巨佬,a数组开到1000000后100了