Cod sursa(job #338498)

Utilizator johnyJohny Deep johny Data 5 august 2009 20:52:44
Problema Secventa Scor 80
Compilator fpc Status done
Runda Arhiva de probleme Marime 0.83 kb
{ 100 p!!!}
program secventa;
var
  A,q: array[1..500000] of longint;
  N,k,i,st,dr,poz,rez: longint;
  f: text;
begin
  assign(f,'secventa.in');
  reset(f);
  readln(f,n,k);
  {initializari coada}
  st:=1; dr:=0;rez:=-31000;

  for i:=1 to k-1 do
  begin
    read(f,a[i]);
    while (dr>=st)and(a[i]<=a[q[dr]]) do dec(dr);
    inc(dr);
    q[dr]:=i;
  end;
  {parcurgem sirul si adaugam/stergem
  elementele in/din coada}
  for i:=k to n do
  begin
    read(f,a[i]);
    {adaugam a[i]}
    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;
  close(f);
  assign(f,'secventa.out');
  rewrite(f);
  write(f,poz-k+1,' ',poz,' ',rez);
  close(f);
end.