Cod sursa(job #169161)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 1 aprilie 2008 11:58:06
Problema Secventa Scor 80
Compilator fpc Status done
Runda Arhiva de probleme Marime 0.72 kb
var a,q:array[1..500000] of longint;   
n,k,i,st,dr,rez,poz:longint;   
f,g:text;   
begin  
assign(f,'secventa.in'); reset(f);   
assign(g,'secventa.out'); rewrite(g);   
read(f,n,k);   
for i:=1 to n do  
  read(f,a[i]);   
rez:=-2000000000;   
st:=1;   
dr:=0;   
for i:=1 to k-1 do begin  
while(dr>=st) and (a[i]<=a[q[dr]]) do  
  dr:=dr-1;   
  dr:=dr+1;   
  q[dr]:=i;   
end;   
for i:=k to n do begin  
  while(dr>=st) and (a[i]<=a[q[dr]]) do  
  dr:=dr-1;   
  dr:=dr+1;   
  q[dr]:=i;   
  while (st<=dr) and (q[st]<i-k+1) do  
   inc(st);   
  if a[q[st]]>rez then begin  
   rez:=a[q[st]];   
   poz:=i;   
  end;   
end;   
writeln(g,poz-k+1,' ',poz,' ',rez);   
close(f); 
close(g);   
end.