Pagini recente » Cod sursa (job #1114132) | Cod sursa (job #3139913) | Cod sursa (job #2421603) | Cod sursa (job #2313674) | Cod sursa (job #327990)
Cod sursa(job #327990)
#include <cstdio>
#include <string.h>
#define FIN "secventa.in"
#define FOUT "secventa.out"
long p, x, n, k, i=0, st, dr, rez, poz=0, a[500000], q[500000], lung;
char s[3500000];
int main()
{
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
scanf("%ld %ld\n", &n, &k);
fgets(s,3500000,stdin);
lung=strlen(s)-1;
while (i<lung)
{
p=1; x=0;
if (s[i]=='-')
{
p=-1;
++i;
}
for ( ; (s[i]!=' ')&&(i<lung); ++i)
{ x=x*10+s[i]-48; }
++poz;
a[poz]=x*p;
++i;
}
rez=-2000000000;
st=1;
dr=0;
for (i=1; i<k; i=i+1)
{
while ((dr>=st) and (a[i]<=a[q[dr]]))
{
dr=dr-1;
}
dr=dr+1;
q[dr]=i;
}
for (i=k; i<=n; i=i+1)
{
while ((dr>=st) and (a[i]<=a[q[dr]]))
{
dr=dr-1;
}
dr=dr+1;
q[dr]=i;
while ((st<=dr) and (q[st]<i-k+1))
{
st=st+1;
}
if (a[q[st]]>rez)
{
rez=a[q[st]];
poz=i;
}
}
printf("%ld %ld %ld\n", poz-k+1, poz, rez);
fclose(stdin); fclose(stdout);
return 0;
}