Pagini recente » Cod sursa (job #1591006) | Cod sursa (job #1590626) | Cod sursa (job #495806) | Cod sursa (job #2680896) | Cod sursa (job #374575)
Cod sursa(job #374575)
#include <cstdio>
char s[10000000];
int y,j,nr,semn,st,dr,n,k;
int a[5000001],dq[5000001];
inline void stanga(int i)
{
if (dq[st]==i-k)
st=st+1;
}
void dreapta (int i)
{
while (st<=dr && a[i]<=a[dq[dr]])
dr=dr-1;
dq[++dr]=i;
}
int main ()
{
int max,i,x;
freopen ("secventa.in","r",stdin);
freopen ("secventa.out","w",stdout);
scanf("%d%d\n",&n,&k);
gets(s);
for (j=0;s[j];j++)
{
if (s[j]=='-')
{
semn=-1;
continue;
}
if (s[j]==' ')
{
a[++nr]=x*semn;
x=0;
semn=1;
continue;
}
x=x*10+s[j]-'0';
}
if(nr!=n)
a[++nr]=x*semn;
for (i=1;i<=k;i++)
dreapta(i);
max=a[dq[st]];
y=1;
for (i=k+1;i<=n;i++)
{
stanga(i);
dreapta(i);
if(a[dq[st]]>max)
{
max=a[dq[st]];
y=i-k+1;
}
}
printf("%d %d %d",y,y+k-1,max);
return 0;
}