Pagini recente » Cod sursa (job #299045) | Cod sursa (job #2079171) | Cod sursa (job #2638862) | Cod sursa (job #1683390) | Cod sursa (job #123932)
Cod sursa(job #123932)
#include <stdio.h>
#define l 500001
int n,k,i,j,t,p1,p2,max;
int a[l],coada[l],poz[l];
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
scanf("%d%d",&n,&k);
for (i=1; i<=k; i++)
scanf("%d",&a[i]);
coada[0]=-32000;poz[1]=1;
coada[1]=a[1];t=1;
for (i=2; i<=k; i++)
{
t++;
coada[t]=a[i];
poz[t]=i;
while (coada[t]<coada[t-1])
{
coada[t-1]=coada[t];poz[t-1]=poz[t];
coada[t]=0;poz[t]=0;
t--;
}
}
max=coada[1];
p1=1;p2=k;
int linf=1;
for (i=k+1; i<=n; i++)
{
scanf("%d",&a[i]);
t++;
coada[t]=a[i];
poz[t]=i;
if (poz[linf]<i-k+1) linf++;
while (coada[t]<coada[t-1] || poz[t-1]<i-k+1 && t>1)
{
coada[t-1]=coada[t];poz[t-1]=poz[t];
coada[t]=0;poz[t]=0;
t--;
}
if (t<linf) linf=t;
if (coada[linf]>max)
{
max=coada[linf];
p1=i-k+1;
p2=i;
}
}
printf("%d %d %d\n",p1,p2,max);
return 0;
}