Pagini recente » Diferente pentru blog/viata-dupa-olimpiade-3 intre reviziile 5 si 6 | Atasamentele paginii Clasament fanninfo | Monitorul de evaluare | Atasamentele paginii oji2014 | Cod sursa (job #79244)
Cod sursa(job #79244)
#include<stdio.h>
#include<limits.h>
long long n, k, i, st, dr, rez, poz, a[500001], q[500001], nr;
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
scanf("%lld %lld",&n,&k);
int ind, x;
char sir[1024];
fgets(sir, 1024, stdin), x = ind = 0;
for(; sir[ind] >= '0' && sir[ind] <= '9'; ind++)
{ x = x*10+(sir[ind]-'0'); a[++nr]=x;}
/* scanf("%lld %lld",&n,&k);
for (i=1; i<=n; i++)
scanf ("%lld",&a[i]);*/
rez=LONG_MIN;
st=1, dr=0;
for (i=1; i<=k-1; i++)
{
while(dr>=st && a[i]<=a[q[dr]]) dr--;
dr++;
q[dr]=i;
}
for (i=k; i<n; i++)
{
while (st<=dr && a[i]<=a[q[dr]]) dr--;
dr++;
q[dr]=i;
while (st<=dr && q[st]<i-k+1) st++;
if (a[q[st]]>rez)
{
rez=a[q[st]];
poz=i;
}
}
printf("%lld %lld %lld",poz-k+1, poz, rez);
return 0;
}