Pagini recente » Cod sursa (job #2233600) | Cod sursa (job #232937) | Cod sursa (job #2372818) | Cod sursa (job #798823) | Cod sursa (job #179004)
Cod sursa(job #179004)
//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.