Cod sursa(job #49316)

Utilizator CezarMocanCezar Mocan CezarMocan Data 5 aprilie 2007 18:21:18
Problema Secventa Scor 20
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.33 kb
var i,j,n,jmin,smin,rez,k,sa,st:integer;
    v,p:array[1..500000]of integer;
    min:array[1..500000]of integer;

begin
assign(input,'secventa.in');reset(input);
assign(output,'secventa.out');rewrite(output);
readln(n,k);
for i:=1 to n do
    read(v[i]);
smin:=1;
min[1]:=v[1];
jmin:=1;
for i:=2 to k do
    begin
    if (v[i]>=min[smin])and(smin<k) then
       begin
       inc(smin);
       min[smin]:=v[i];
       p[smin]:=i;
       end
    else
        begin
        while (min[smin]>v[i])and(smin>0) do
              dec(smin);
        inc(smin);
        min[smin]:=v[i];
        p[smin]:=i;
        end;
    end;
rez:=-maxint;
if min[jmin]>rez then
        begin
        rez:=min[jmin];
        sa:=1;
        st:=k;
        end;
for i:=k+1 to n do
    begin
    if (v[i]>=min[smin])and(smin<k) then
       begin
       inc(smin);
       min[smin]:=v[i];
       p[smin]:=i;
       end
    else
        begin
        while (min[smin]>v[i])and(smin>=jmin) do
              dec(smin);
        inc(smin);
        min[smin]:=v[i];
        p[smin]:=i;
        end;
    if v[i-k]=min[jmin] then
       inc(jmin);
    if (min[jmin]>rez) then
        begin
        rez:=min[jmin];
        sa:=i-k+1;
        st:=i;
        end;
    end;
writeln(sa,' ',st,' ',rez);
close(input);close(output);
end.