Pagini recente » Cod sursa (job #2024372) | Cod sursa (job #2123751) | Cod sursa (job #3258056) | Cod sursa (job #2406514) | Cod sursa (job #374564)
Cod sursa(job #374564)
#include<cstdio>
int n,k,st,dr,j,min,mini,semn,x,nr;
int dq[500001];
int v[500001];
char s[1000000];
inline void stanga(int i)
{
if (dq[st]==i-k)
++st;
}
void dreapta (int i)
{
while(st<=dr && v[i]<=v[dq[dr]] )
--dr;
dq[++dr]=i;
}
int main()
{
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]==' ')
{
v[++nr]=x*semn;
x=0;
semn=1;
continue;
}
x=x*10+s[j]-'0';
}
if (nr!=n)
v[++nr]=x*semn;
st=1;
dr=0;
for (j=1;j<=k;j++)
{
//stanga(j);
dreapta(j);
}
for (j=k;j<=n;j++)
{
stanga(j);
dreapta(j);
if (v[dq[st]]>min)
{
min=v[dq[st]];
mini=j-k+1;
}
}
printf("%d %d %d", mini, mini+k-1, min);
return 0;
}