forever_shi @ 2017-10-30 16:36:02
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
struct node
{
int x,p;
}e[1000001],l[1000001];
int n,m,a[1000001],head=1,tail=1;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
l[1].x=a[1];
l[1].p=1;
for(int i=2;i<=n;i++)
{
while(head<=tail&&l[tail].x>=a[i])
tail--;
tail++;
l[tail].x=a[i];
l[tail].p=i;
while(l[head].p<i-m+1)
head++;
if(i>=m)
printf("%d ",l[head].x);
}
cout<<endl;
tail=1;
head=1;
e[1].x=a[1];
e[1].p=1;
for(int i=2;i<=n;i++)
{
while(head<=tail&&e[tail].x<=a[i])
tail--;
tail++;
e[tail].x=a[i];
e[tail].p=i;
while(e[head].p<i-m+1)
head++;
if(i>=m)
printf("%d ",e[head].x);
}
return 0;
}
//本程序90分,第三个点WA了,测评数据下不来,所以蒟蒻不知所措了
by night @ 2017-11-02 11:41:02
第三个点k=1
by _小妖 @ 2017-11-08 18:47:13
嗯,谢谢楼上,蒟蒻在判断范围的时候加一个head<=tail的条件就好了