Cod sursa(job #346536)

Utilizator ionutz32Ilie Ionut ionutz32 Data 8 septembrie 2009 14:48:39
Problema Secventa Scor 20
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.27 kb
var v,dq:array[1..500000] of integer;
n,k,i,hi,a,b,m,min,h1,h2,x:longint;
f,g:text;
begin
assign(f,'secventa.in');
assign(g,'secventa.out');
reset(f);rewrite(g);
readln(f,n,k);
for i:=1 to n do
    read(f,v[i]);
min:=-maxlongint;
for i:=1 to n do
    begin
    while (1<=hi) and (v[dq[hi]]>=v[i]) do
          dec(hi);
    inc(hi);
    dq[hi]:=i;
    if i>=k then
       begin
       a:=1;
       b:=hi;
       while a<=b do
             begin
             m:=a+(b-a) shr 1;
             if dq[m]>=i-k+1 then
                b:=m-1
             else
                 a:=m+1;
             end;
       if v[dq[b+1]]>min then
          begin
          min:=v[dq[b+1]];
          if b>0 then
             h1:=dq[b]+1
          else
              h1:=1;
          h2:=i;
          end
       else
           if v[dq[b+1]]=min then
              begin
              if b>0 then
                 x:=dq[b]+1
              else
                  x:=1;
              if x<h1 then
                 begin
                 h1:=x;
                 h2:=i;
                 end
              else
                  if (x=h1) and (i<h2) then
                     h2:=i;
              end;
       end;
    end;
write(g,h1,' ',h2,' ',min);
close(f);close(g);
end.