Cod sursa(job #772647)

Utilizator hungntnktpHungntnktp hungntnktp Data 30 iulie 2012 13:19:12
Problema Secventa Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.34 kb
USES
        math;
CONST
        tfi     =       'secventa.in';
        tfo     =       'secventa.out';
        nmax    =       500000;
TYPE
        arr1    =       array [0..nmax] of longint;
VAR
        fi,fo           :       text;
        n,k,f,r,d,c     :       longint;
        res             :       int64;
        a,q             :       arr1;
Procedure mo;
  begin
        assign(fi,tfi);reset(fi);
        assign(fo,tfo);rewrite(Fo);
  End;
Procedure dong;
  Begin
        close(fi);
        close(fo);
  End;
Procedure nhap;
  var
        i       :       longint;
  Begin
        read(fi,n,k);
        for i:=1 to n do read(fi,a[i]);
  End;
Function find(x:longint):longint;
  var
        i,j,mid,t:       longint;
  Begin
        i:=f;
        j:=r;
        t:=0;
        while i<=j do
          begin
                 mid:=(i+j) div 2;
                 if a[q[mid]]>x then
                   begin
                          t:=mid;
                          j:=mid-1;
                   end
                 else i:=mid+1;
          end;
        exit(t);
  End;
Procedure push(x:longint);
  Begin
        inc(r);
        q[r]:=x;
  End;
procedure xuly;
  var
        i,j     :       longint;
  Begin
        f:=1;
        r:=0;
        push(1);
        for i:=1 to n do
          begin
                 if a[i]>a[q[r]] then push(i);
                 if f<=r then
                   begin
                         j:=find(a[i]);
                         if j>0 then
                           begin
                                  d:=q[j];
                                  r:=j;
                                  q[r]:=i;
                           end;
                         while (f<r) and (q[f]<=i-k) do inc(f);
                           if i>=k then
                             if res<a[q[f]] then
                               begin
                                       res:=a[q[f]];
                                       if d>0 then d:=min(d,q[f])
                                       else d:=q[f];
                                       c:=i;
                               end;
                  end;
          end;
        write(fo,d,' ',c,' ',res);
  End;
BEGIN
        mo;
        nhap;
        xuly;
        dong;

END.