Pagini recente » Cod sursa (job #846492) | Cod sursa (job #3218051) | Cod sursa (job #1523120) | Cod sursa (job #96895) | Cod sursa (job #47484)
Cod sursa(job #47484)
//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.