Pagini recente » Monitorul de evaluare | Cod sursa (job #13139) | Cod sursa (job #1616462) | Cod sursa (job #129017) | Cod sursa (job #289413)
Cod sursa(job #289413)
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define DIM 500005
#define INF -30005
int a[DIM],b[DIM];
char c[DIM/10000*DIM];
int n,k,nrt,in,t;
void read ()
{
int i,nr=0,ok=1;
scanf ("%d%d\n",&n,&k);
gets (c);
t=strlen (c);
n=0;
for (i=0; i<t; ++i)
if (isdigit (c[i]))
nr=nr*10+c[i]-'0';
else if (c[i]=='-')
ok=-1;
else
{
a[++n]=nr*ok;
nr=0;
ok=1;
}
if (nr)
a[++n]=nr;
}
void solve ()
{
int st=1,dr=0,i;
for (i=1; i<k; ++i)
{
while (st<=dr && a[i]<=a[b[dr]])
--dr;
b[++dr]=i;
}
for (i=k, nrt=INF; i<=n; ++i)
{
while (st<=dr && a[i]<=a[b[dr]])
--dr;
b[++dr]=i;
while (st<=dr && b[st]<i-k+1)
++st;
if (a[b[st]]>nrt)
{
nrt=a[b[st]];
in=i;
}
}
printf ("%d %d %d",in-k+1,in,nrt);
}
int main ()
{
freopen ("secventa.in","r",stdin);
freopen ("secventa.out","w",stdout);
read ();
solve ();
return 0;
}