Cod sursa(job #772636)
Utilizator | 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.