Cod sursa(job #772636)

Utilizator hungntnktpHungntnktp hungntnktp Data 30 iulie 2012 13:13:39
Problema Secventa Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.36 kb
Uses windows;
{$inline on}
Const
        finp='secventa.in';
        fout='secventa.out';
Type
        mat=array [0..500000] of longint;
Var     a,stack,dau,cuoi,min:mat;
        n,k,d,c,res,f,r:longint;
        time:longint;
        fi,fo:text;

Procedure Doc;   inline;
        Var i:longint;
        Begin
                Assign(fi,finp);
                Reset(fi);
                Read(fi,n,k);
                For i:=1 to n do Read(fi,a[i]);
                Close(fi);
        end;

Procedure Push(x:longint);    inline;
        Begin
                inc(r);
                stack[r]:=x;
        end;

Procedure Lam;    inline;
        Var i:longint;
        Begin
                f:=1;
                r:=0;
                For i:=1 to n do
                  Begin
                        While (f<=r) and (a[i]<a[stack[r]]) do dec(r);
                        Push(i);
                        If stack[f]=i-k then inc(f);
                        If i>=k then
                                Begin
                                        dau[i]:=i-k+1;
                                        cuoi[i]:=i;
                                        min[i]:=a[stack[f]];
                                end;
                  end;
                res:=-maxlongint;
                For i:=k to n do
                  If res<min[i] then
                     Begin
                        d:=dau[i];
                        c:=cuoi[i];
                        res:=min[i];
                     end;
                For i:=k to n do
                  If res=min[i] then
                    Begin
                        If d>dau[i] then
                             Begin
                                d:=dau[i];
                                c:=cuoi[i];
                             end
                        Else
                          If c>cuoi[i] then c:=cuoi[i];
                    end;
                While (d>1) and (a[d-1]>=res) do dec(d);
        end;

Procedure Inkq;    inline;
        Begin
                Assign(fo,fout);
                Rewrite(fo);
                Write(fo,d,' ',c,' ',res);
                Close(fo);
        end;

        Begin
                time:=gettickcount;
                Doc;
                Lam;
                Inkq;
                Write((gettickcount-time)/1000);
        end.