Cod sursa(job #287390)

Utilizator cristinabCristina Brinza cristinab Data 24 martie 2009 20:14:04
Problema Secventa Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.05 kb
{secventa inf oarena}

var a:array[1..500000] of longint;
    q:array[0..500000] of longint;
    n,k,rez,poz:longint;
    g:text;

procedure citire;
var i:longint;
    f:text;
begin

assign(f,'secventa.in'); reset(f);

readln(f,n,k);

for i:=1 to n do read(f,a[i]);

close(f);
end;

procedure rezolvare;
var i,j,stanga,dreapta:longint;

begin

rez:=0;
poz:=0;
stanga:=1;
dreapta:=0;

for i:=1 to k-1 do
    begin
    while (stanga<=dreapta) and (a[i]<=a[q[dreapta]]) do dec(dreapta);
    inc(dreapta);
    q[dreapta]:=i;
    end;

for i:=k to n do
    begin
    while (stanga<=dreapta) and (a[i]<=a[q[dreapta]]) do dec(dreapta);
    inc(dreapta);
    q[dreapta]:=i;

    while (stanga<=dreapta) and (q[stanga]<i-k+1) do inc(stanga);

    if a[q[stanga]]>rez then
       begin
       rez:=a[q[stanga]];
       poz:=i;
       end
    else if (a[q[stanga]]=rez) and (i<poz) then poz:=i;
    end;

assign(g,'secventa.out'); rewrite(g);
writeln(g,poz-k+1,' ',poz,' ',rez);
close(g);
end;

begin
citire;
rezolvare;
end.