Cod sursa(job #186432)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 27 aprilie 2008 22:15:50
Problema Secventa Scor 80
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.43 kb
const inf=500001;
      cif:array['0'..'9']of integer=(0,1,2,3,4,5,6,7,8,9);

var fi,fo:text;
    n,k,i,start,stop,poz,min:longint;
    v,deque:array[0..500000]of longint;

procedure parsare;
var i,ct,aux,semn:longint;
    s:ansistring;
begin
  readln(fi,s);
  s:=s+' ';
  ct:=0;
  aux:=0;
  semn:=1;
  for i:=1 to length(s) do
    begin
      if s[i]='-' then semn:=-1
       else
         if s[i]=' ' then
           begin
             inc(ct);
             if semn=-1 then v[ct]:=-aux
                        else v[ct]:=aux;
             semn:=1;
             aux:=0;
           end
         else
           aux:=aux*10+cif[s[i]];
    end;

end;

begin
  assign(fi,'secventa.in'); reset(fi);
  assign(fo,'secventa.out'); rewrite(fo);
  readln(fi,n,k);
  parsare;
  start:=1;
  stop:=0;
  v[0]:=-inf;
  for i:=1 to k do
    begin
      while v[deque[stop]]>v[i] do
        dec(stop);
      inc(stop);
      deque[stop]:=i;
    end;
  min:=v[deque[start]];
  poz:=k;
  for i:=k+1 to n do
    begin
      while deque[start]<i-k+1 do
        inc(start);
      while v[deque[stop]]>v[i] do
        if stop<>start-1 then dec(stop)
                         else break;
      inc(stop);
      deque[stop]:=i;
      if v[deque[start]]>min then
        begin
          min:=v[deque[start]];
          poz:=i;
        end;
    end;
  writeln(fo,poz-k+1,' ',poz,' ',min);
  close(fi);
  close(fo);
end.