Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

运行错误,求救

Posted by yedeming at 2010-03-06 20:17:16 on Problem 2082
var n,i,j,x,y,z:longint;
    tmp,best:int64;
    w,h,fa,left,right,num,h1:array[0..50005]of longint;
    sum:array[0..50005]of int64;
function find(x:longint):longint;
var r:longint;
begin
    find:=x;
    while find<>fa[find] do find:=fa[find];
    while x<>fa[x] do begin
        r:=x;
        x:=fa[x];
        fa[r]:=find;
    end;
end;
procedure sort(x,y:longint);
var i,j,k:longint;
begin
    i:=x;j:=y;k:=h1[(x+y)shr 1];
    while i<j do begin
        while h1[i]>k do inc(i);
        while h1[j]<k do dec(j);
        if i<=j then begin
            h1[0]:=h1[i];h1[i]:=h1[j];h1[j]:=h1[0];
            num[0]:=num[i];num[i]:=num[j];num[j]:=num[0];
            inc(i);dec(j);
        end;
    end;
    if i<y then sort(i,y);
    if j>x then sort(x,j);
end;
procedure he(x,y:longint);
begin
    if x=y then exit;
    fa[y]:=x;
    if left[y]<left[x] then left[x]:=left[y];
    if right[y]>right[x] then right[x]:=right[y];
end;
begin
    while true do begin
        fillchar(left,sizeof(left),0);
        fillchar(right,sizeof(right),0);
        fillchar(w,sizeof(w),0);
        fillchar(h,sizeof(h),0);
        fillchar(h1,sizeof(h1),0);
        fillchar(sum,sizeof(sum),0);
        fillchar(fa,sizeof(fa),0);
        readln(n);
        if n=-1 then break;
        sum[0]:=0;
        for i:=1 to n do begin
            readln(w[i],h[i]);
            h1[i]:=h[i];
            sum[i]:=sum[i-1]+w[i];
            fa[i]:=i;
            num[i]:=i;
            left[i]:=i;right[i]:=i;
        end;
        sort(1,n);
        best:=0;
        for i:=1 to n do begin
            z:=find(num[i]);
            if (z<>1)and(h[left[z]-1]>=h[num[i]]) then
            x:=find(left[z]-1) else x:=0;
            if (right[z]<>n)and(h[right[z]+1]>=h[num[i]]) then
            y:=find(right[z]+1) else y:=0;
            if (y<>0)and(x<>0) then begin
                he(z,y);
                he(x,z);
                tmp:=(sum[right[x]]-sum[left[x]-1])*h1[i];
            end else if (x=0)and(y<>0) then begin
                he(z,y);
                tmp:=(sum[right[z]-sum[left[z]-1]])*h1[i];
            end
            else if (x<>0)and(y=0) then begin
                he(x,z);
                tmp:=(sum[right[x]]-sum[left[x]-1])*h1[i];
            end
            else tmp:=w[num[i]]*h1[i];
            if tmp>best then best:=tmp;
        end;
        writeln(best);
    end;
end.
谢

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator