Cod sursa(job #179004)

Utilizator ovy2906Popescu Ovidiu ovy2906 Data 15 aprilie 2008 14:40:53
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
//infoarena secventa
const max = 500001;
type rec = record
                poz:longint;
                val :  longint;
                end;
var deque : array[1..max] of rec;
    secv : array[1..max] of longint;
    d1,d2,n,k, solstart, solstop, solmin : longint;
    c:char;
    f:text;


function getnn:longint;
var rez:longint;
    neg: boolean;
begin
rez:=0; neg:=false;
if c = '-' then begin neg:=true; read(f,c); end;
while ((ord(c) >=48) and (ord(c) <= 57)) do
        begin
        rez:=rez*10 + ord(c) - 48;
        read(f,c);
        end;
if neg then rez:=-rez;
getnn:=rez;
while (((ord(c)  < 48) or ( ord(c) > 57))) and ( ord(c) <> 26) and ( c <> '-')  do
       read(f,c);
end;


procedure citire;
var i: longint;
    buf : array[1..32768] of byte;
begin
assign(f,'secventa.in'); reset(f); settextbuf(f,buf);
readln(f,n,k); read(f,c);
for i:=1 to n do
        secv[i]:=getnn;
close(f);
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 >= k )  then
                if (deque[d1].val > solmin )then
                        begin
                        solmin:=deque[d1].val;
                        solstart:=i-k+1;
                        solstop:=i;
                        end;
        end;
end;


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