Cod sursa(job #184715)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 24 aprilie 2008 09:47:05
Problema Secventa Scor 80
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.01 kb
var a,q:array[1..500000] of longint;
    n,k,i,st,dr,rez,poz:longint;
    f,g:text;

procedure citire;
 var x,p,poz:longint;
     ch:char;
 begin
  read(f,ch); x:=0; p:=1; poz:=0;
  while not(eoln(f)) do begin
   if ch='-' then
    p:=-1
   else
    if ch<>' ' then
     x:=x*10+ord(ch)-48
    else begin
     inc(poz);
     a[poz]:=x*p;
     x:=0;
     p:=1;
    end;
   read(f,ch);
  end;
  x:=x*10+ord(ch)-48;
  inc(poz);
  a[poz]:=x*p;
 end;

begin
 assign(f,'secventa.in'); reset(f);
 assign(g,'secventa.out'); rewrite(g);
 readln(f,n,k);
 citire;
 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.