Pagini recente » Cod sursa (job #980903) | Cod sursa (job #1951688) | Cod sursa (job #993696) | Cod sursa (job #669191) | Cod sursa (job #180296)
Cod sursa(job #180296)
#include <stdio.h>
#define maxl 500010
#include <string.h>
int i,j,k,n,l,r,max=-30010,p,q,semn;
int dec[maxl],val[maxl];
char s[4000010];
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
scanf("%d %d\n",&n,&k);l=k;
/* for (i=1; i<=n; i++)
scanf("%d ",&val[i]); */
fgets(s,4000000,stdin);
i=0;k=strlen(s)-1;q=0;
while (i<k)
{
semn=1;p=0;
if (s[i]=='-') { semn=-1;i++;}
while (s[i]!=' ' && i<k)
{
p=p*10+s[i]-48;
i++;
}
i++;
q++;
val[q]=p*semn;
}
val[0]=-30010;k=l;
for (i=1; i<=k; i++)
{
r++;
dec[r]=i;
while (val[dec[r-1]]>val[dec[r]])
{
dec[r-1]=dec[r];
r--;
}
}
max=val[dec[1]];p=1;q=k;
l=1;
for (i=k+1; i<=n; i++)
{
if (dec[l]<=i-k)
{
dec[l]=-30100;
l++;
}
r++;
dec[r]=i;
while (r-1>=l && val[dec[r-1]]>val[dec[r]])
{
dec[r-1]=dec[r];
r--;
}
if (val[dec[l]]>max)
{
max=val[dec[l]];p=i-k+1;q=i;
}
}
printf("%d %d %d\n",p,q,max);
return 0;
}