Pagini recente » Cod sursa (job #1665203) | Cod sursa (job #794248) | Cod sursa (job #618289) | Cod sursa (job #1013198) | Cod sursa (job #258151)
Cod sursa(job #258151)
#include <stdio.h>
#define NR 500005
int n,k,max,u,p,a,b;
char s[7*NR];
int v[NR],deq[NR];
void read()
{
scanf("%d%d\n",&n,&k);
gets(s);
//puts(s);
int i,nr=0,semn=1,x=0;
for (i=0; s[i]; ++i)
{
if (s[i]==' ')
{
v[++nr]=semn*x;
x=0;
semn=1;
}
if (s[i]=='-')
semn=-1;
if (s[i]>='0' && s[i]<= '9')
x=x*10+(s[i]-'0');
}
if(x)
v[++nr]=semn*x;
}
void stanga(int i)
{
if (i-deq[p]>=k)
++p;
}
void dreapta(int i)
{
while (u!=p && v[deq[u-1]]>=v[i])
--u;
deq[u++]=i;
}
/*void proba()
{
for(int i=1;i<=n;++i)
printf("%d ",v[i]);
printf("\n");*/
//}
void solve()
{
int i;
//deq[u++]=1;
for (i=1; i<=k; i++)
dreapta(i);
max=v[deq[p]];
for (i=k+1; i<=n; ++i)
{
stanga(i);
dreapta(i);
if (v[deq[p]]>max)
{
max=v[deq[p]];
a=i-k+1;
b=i;
}
}
printf("%d %d %d",a,b,max);
}
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
read();
//proba();
solve();
return 0;
}