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