## poj2452

2018年04月26日 ⁄ 综合 ⁄ 共 1264字 ⁄ 字号 评论关闭

【题意】

【输入】

【输出】

```program poj2452;
type
arr=array [0..16,0..50001] of longint;
var
n,i,j,k,s,e,ans,mid:longint;
p:array [0..50001] of longint;
max,min:arr;

function wmax (a,b:longint;var max:arr;x:longint):longint;
var
k:longint;
begin
if a=b then exit(p[a]);
k:=trunc(ln(b-a+1)/ln(2));
if max[k,a]*x>max[k,b-(1 shl k)+1]*x then exit(max[k,a])
else exit(max[k,b-(1 shl k)+1]);
end;

procedure st (var max:arr;x:longint);
begin
for i:=1 to n do
max[0,i]:=p[i];
k:=0;
while 1 shl k<n do
begin
for i:=1 to n do
if i+(1 shl k)>n then max[k+1,i]:=max[k,i]
else
if max[k,i]*x>max[k,i+(1 shl k)]*x then max[k+1,i]:=max[k,i]
else max[k+1,i]:=max[k,i+(1 shl k)];
inc(k);
end;
end;

begin
while not seekeof do
begin
for i:=1 to n do
if n<=1 then
begin
writeln(-1);
continue;
end;
st(max,1);
st(min,-1);
ans:=0;
for i:=1 to n-1 do
begin
if p[i+1]<=p[i] then continue;
s:=i+1;
e:=n;
while s<>e do
begin
mid:=s+e-(s+e) div 2;
if wmax(i+1,mid,min,-1)>p[i] then s:=mid
else e:=mid-1;
end;
k:=wmax(i+1,s,max,1);
if p[i+1]=k then
begin
if ans<1 then ans:=1;
continue;
end;
s:=i+2;
while s<>e do
begin
mid:=s+e-(s+e) div 2;
if wmax(i+1,mid-1,max,1)<k then s:=mid
else e:=mid-1;
end;
if e-i>ans then ans:=e-i;
end;
if ans=0 then writeln(-1)
else writeln(ans);
end;
end.

```
【上篇】
【下篇】