Cod sursa(job #31258)

Utilizator CezarMocanCezar Mocan CezarMocan Data 15 martie 2007 18:37:01
Problema Secventa Scor 70
Compilator fpc Status done
Runda Arhiva de probleme Marime 0.65 kb
var n,k,i,st,dr,rez,poz:longint;
    a,q:array[0..500000]of longint;
begin
  assign(input,'secventa.in');reset(input);
  assign(output,'secventa.out');rewrite(output);
  readln(n,k);
  for i:=1 to n do read(a[i]);
  rez:=-maxlongint;
  st:=1;dr:=0;
  for i:=1 to k-1 do begin
    while (dr>=st)and(a[i]<=a[q[dr]])do dec(dr);
    inc(dr);
    q[dr]:=i;
  end;
  for i:=k to n do begin
    while (st<=dr)and(a[i]<=a[q[dr]]) do dec(dr);
    inc(dr);
    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(poz-k+1,' ',poz,' ',rez);
  close(input);close(output);
end.