Pagini recente » Cod sursa (job #585318) | Cod sursa (job #923529) | Cod sursa (job #2215790) | Cod sursa (job #1750665) | Cod sursa (job #374553)
Cod sursa(job #374553)
#include<cstdio>
int n,k,st,dr,j,min,mini,semn;
int dq[500001];
int v[500001];
char s[100000];
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;
else if (s[j]!=' ')
{
if (semn)
v[++v[0]]=0 - (v[v[0]]*10 + s[j] - '0');
else v[++v[0]]=v[v[0]]*10 + s[j] - '0';
semn=0;
}
}
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=dq[st];
}
}
printf("%d %d %d", mini, mini+k-1, min);
return 0;
}