Mai intai trebuie sa te autentifici.

Cod sursa(job #772643)

Utilizator hungntnktpHungntnktp hungntnktp Data 30 iulie 2012 13:18:33
Problema Secventa Scor 60
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.5 kb
CONST tfi='secventa.in';
      tfo='secventa.out';
VAR fo,fi:text;
    N,k,l,r:longint;
    r1,r2:longint;
    res:Int64;
    a,st:array[1..500000] of longint;
    min,x,y:array[1..500000] of longint;
procedure nhap;
  var i:longint;
  begin
       assign(fi,tfi);reset(fi);
       assign(fo,tfo);rewrite(fo);
         read(fi,n,k);
         for i:=1 to n do read(fi,a[i]);
       close(fi);
  end;
procedure push(i:longint);
  begin
        while (l<=r) and (a[i]<=a[st[r]]) do Dec(r);
        Inc(r);
        st[r]:=i;

  end;
procedure Xuli;
  var i,j:longint;
  begin
       l:=1;r:=0;res:=-15000000000;
       r1:=MaxLongint;r2:=r1;
       For i:=1 to n do
          begin
                push(i);
                while (l<=r) and (st[l]<=i-k) do Inc(l);
                if i>=k then
                  begin
                        min[i]:=a[st[l]];
                        x[i]:=i-k+1;
                        y[i]:=i;
                  end;
          end;
        For i:=k to n do
         if min[i]>res then
          begin
                res:=min[i];
                r1:=x[i];
                r2:=y[i];
          end
         else if min[i]=res then
           begin
                 if x[i]<r1 then r1:=x[i]
                 else if x[i]=r1 then
                   begin
                        if y[i]<r2 then r2:=y[i];
                   end;
           end;
        write(fo,r1,' ',r2,' ',res);
        close(fo);
  end;
BEGIN
      nhap;
      Xuli;
END.