Cod sursa(job #186430)

Utilizator Pepelea_FlaviuFlaviu Pepelea Pepelea_Flaviu Data 27 aprilie 2008 22:08:07
Problema Secventa Scor 70
Compilator fpc Status done
Runda Arhiva de probleme Marime 0.91 kb
const inf=500001;

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

begin
  assign(fi,'secventa.in'); reset(fi);
  assign(fo,'secventa.out'); rewrite(fo);
  read(fi,n,k);
  for i:=1 to n do
    read(fi,v[i]);
  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.