Pagini recente » Cod sursa (job #1271285) | Cod sursa (job #1244232) | Monitorul de evaluare | Cod sursa (job #2006088) | Cod sursa (job #341346)
Cod sursa(job #341346)
#include<cstdio>
#define N 500002
int n,k,v[N],p,u,maxim,sf,inc,d[N],num;
char s[N<<3];
void citire()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
scanf("%d%d\n",&n,&k);
fgets(s,N<<3,stdin);
int nr=0,semn=1;
for (int i=0; s[i]&&s[i]!='\n'; ++i)
{
if (s[i]=='-')
{
semn=-1;
continue;
}
if(s[i]>='0'&&s[i]<='9')
{
nr=nr*10+(s[i]-'0');
continue;
}
v[++num]=nr*semn;
semn=1;nr=0;
}
v[++num]=nr*semn;
for (int i=1; i<=k; ++i)
{
while (p!=u&&v[i]<=v[d[u-1]])
--u;
d[u++]=i;
}
maxim=v[d[p]];
inc=1;
sf=k;
for (int i=k+1; i<=n; ++i)
{
int g=i-d[p];
if (g==k)
++p;
while (u!=p&&v[i]<=v[d[u-1]])
--u;
d[u++]=i;
if (maxim<v[d[p]])
{
maxim=v[d[p]];
inc=i-k+1;
sf=i;
}
}
printf("%d %d %d",inc,sf,maxim);
}
int main()
{
citire();
return 0;
}