Cod sursa(job #47484)

Utilizator andrei_infoMirestean Andrei andrei_info Data 3 aprilie 2007 19:11:36
Problema Secventa Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.37 kb
//infoarena secventa
const max = 500001;
type rec = record
                poz:longint;
                val :  integer;
                end;
var deque : array[1..max] of rec;
    secv : array[1..max] of integer;
    d1,d2,n,k, solstart, solstop, solmin : longint;

procedure citire;
var i: longint;
begin
assign(input,'secventa.in'); reset(input);
readln(n,k);
for i:=1 to n do
        read(secv[i]);
close(input);
end;

procedure solve;
var i:longint;
begin
deque[1].poz:=1; deque[1].val:=secv[1]; d1:=1; d2:=1;
if k = 1 then
        begin
        solstart:=1; solstop:=1; solmin:=secv[1];
        end
else  solmin:=-maxint;

for i:=2 to n do
        begin

        while ( d1 <= d2)  and ( deque[d1].poz <= i-k) do
                d1:=d1+1;
        while ( d2 >= d1) and ( deque[d2].val >= secv[i] ) do
                d2:=d2-1;
        d2:=d2+1;
        deque[d2].poz:=i; deque[d2].val:=secv[i];
        if ( i- deque[d1].poz +1 >= k )  then
                if (deque[d1].val > solmin )then
                        begin
                        solmin:=deque[d1].val;
                        solstart:=deque[d1].poz;
                        solstop:=i;
                        end;
        end;
end;


begin
citire;
solve;
assign(output,'secventa.out'); rewrite(output);
writeln(solstart,' ',solstop,' ',solmin);
close(output);
end.