Cod sursa(job #350397)

Utilizator MKLOLDragos Ristache MKLOL Data 23 septembrie 2009 19:35:27
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include<fstream.h>
#define Nmax 500010

int v[Nmax],dq[Nmax],K,N,st,dr,max=-10000001,ifin,jfin,semn,o,ok;
char car;
int main()
{

freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
scanf("%d %d\n",&N,&K);

o=1;
for(int i=0;i<=N;++i)
{
    if(car=='-')
    {
        semn=-1;
    }

scanf("%c",&car);
    if(car<='9'&&car>='0')
    {ok=1;
        while(car<='9'&&car>='0'&&ok==1)
        {ok=0;
        v[o]=v[o]*10+(car-'0');
        if(scanf("%c",&car)==1) ok=1;
        }
        v[o]=v[o]*semn;
        ++o;
    }
    semn=1;

}

st=1;
dr=0;

for(int i=1;i<=N;++i)
{
while(st<=dr&&v[dq[dr]]>v[i]) --dr;
dq[++dr]=i;

if(dq[st]==i-K)
++st;


if(i>=K)
{
if(v[dq[st]]>max)
{
max=v[dq[st]];
ifin = i-K+1;
jfin = i;
}
}
}

printf("%d %d %d\n",ifin,jfin,max);

return 0;
}