Pagini recente » Cod sursa (job #1694850) | Cod sursa (job #1767874) | Cod sursa (job #1280140) | Cod sursa (job #2018238) | Cod sursa (job #431056)
Cod sursa(job #431056)
#include<cstdio>
#define maxn 500001
#define minim -30000
int maxim,c,n,k,a[maxn],deque[maxn];
void cit()
{
scanf("%d %d",&n,&k);
int i;
for(i=1; i<=n; i++)
scanf("%d",&a[i]);
}
void rez()
{
int inc,sf;
inc=sf=0;
deque[0]=1;
int i;
for(i=2; i<=k; i++)
{
while(a[i]<a[ deque[sf] ] && inc<=sf )
sf--;
if(inc==sf && a[i]<a[deque[inc]])
deque[inc]=i;
else
deque[++sf]=i;
}
maxim=a[deque[inc] ];
c=1;
for(i=k+1; i<=n; i++)
{
int p=0;
if(deque[inc]<=i-k)
inc++;
while(a[deque[sf]]>a[i] && inc<=sf)
{p++; sf--;}
if(inc==sf && a[i]<a[deque[inc]])
deque[inc]=i;
else
deque[++sf]=i;
if(maxim<a[deque[inc]])
{
maxim=a[deque[inc]];
if(sf-inc==0)
c=deque[inc]-k+1;
else
c=deque[inc];//-p;
}
}
}
void afis()
{
printf("%d %d %d",c,c+k-1,maxim);
}
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
cit();
rez();
afis();
return 0;
}