Cod sursa(job #51378)

Utilizator ProtomanAndrei Purice Protoman Data 11 aprilie 2007 19:24:19
Problema Secventa Scor 20
Compilator fpc Status done
Runda Arhiva de probleme Marime 0.82 kb
var a,q:array[1..500000] of Integer; i,ic,d,r,poz,n,k:longint; f1,f2:text;
Begin
        assign(f1,'secventa.in');
        reset(f1);
        assign(f2,'secventa.out');
        rewrite(f2);
        read(f1,n,k);
        for i:=1 to n do read(f1,a[i]);
        r:=-maxlongint;ic:=1;d:=0;
        for i:=1 to k-1 do
        begin
                while (d>=ic)and(a[i]<=a[q[d]]) do dec(d);
                inc(d);
                q[d]:=i;
        end;
        for i:=k to n do
        begin
                while (ic<=d)and(a[i]<=a[q[d]]) do dec(d);
                inc(d);
                q[d]:=i;
                while (ic<=d)and(q[ic]<i-k+1) do inc(ic);
                if a[q[ic]]>r then begin r:=a[q[ic]]; poz:=i; end;
        end;
        write(f2,poz-k+1,' ',poz,' ',r);
        close(f1);
        close(f2);
End.