| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
看看我哪写错了。。。。。。两天了。。。。。。program poj2482;
var
ans:int64;
left,right,a,b,c,t,head,tail,i,j,k,m,n,w,h,tot,xx,yy,p:longint;
x,y:array [0..210000] of int64;
l,r,max,v,z,nowx,nowy,num,other:array [0..210000] of int64;
procedure qsort1(s,t:longint);
var
i,j:longint;
mid,o:int64;
begin
i:=s;
j:=t;
mid:=x[(i+j)shr 1];
repeat
while x[i]<mid do inc(i);
while x[j]>mid do dec(j);
if i<=j then
begin
o:=x[i];x[i]:=x[j];x[j]:=o;
o:=y[i];y[i]:=y[j];y[j]:=o;
o:=num[i];num[i]:=num[j];num[j]:=o;
inc(i);
dec(j);
end;
until i>j;
if s<j then qsort1(s,j);
if i<t then qsort1(i,t);
end;
procedure qsort2(s,t:longint);
var
i,j:longint;
mid,o:int64;
begin
i:=s;
j:=t;
mid:=y[(i+j)shr 1];
repeat
while y[i]<mid do inc(i);
while y[j]>mid do dec(j);
if i<=j then
begin
o:=x[i];x[i]:=x[j];x[j]:=o;
o:=y[i];y[i]:=y[j];y[j]:=o;
o:=num[i];num[i]:=num[j];num[j]:=o;
inc(i);
dec(j);
end;
until i>j;
if s<j then qsort2(s,j);
if i<t then qsort2(i,t);
end;
procedure qsort(s,t:longint);
var
midx,midy,o,oi,oj:int64;
i,j:longint;
begin
i:=s;
j:=t;
midx:=nowx[(i+j)shr 1];
midy:=nowy[(i+j)shr 1];
repeat
while (nowx[i]<midx)or(nowx[i]=midx)and(nowy[i]<midy) do inc(i);
while (nowx[j]>midx)or(nowx[j]=midx)and(nowy[j]>midy) do dec(j);
if i<=j then
begin
o:=nowx[i];nowx[i]:=nowx[j];nowx[j]:=o;
o:=nowy[i];nowy[i]:=nowy[j];nowy[j]:=o;
if other[i]<>j then
begin
oi:=other[i];
oj:=other[j];
other[oi]:=j;
other[oj]:=i;
other[i]:=oj;
other[j]:=oi;
end;
o:=z[i];z[i]:=z[j];z[j]:=o;
inc(i);
dec(j);
end;
until i>j;
if s<j then qsort(s,j);
if i<t then qsort(i,t);
end;
function max0(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure build(node,left,right:longint);
begin
l[node]:=left;
r[node]:=right;
max[node]:=0;
v[node]:=0;
if left=right then exit;
build(node*2,left,(left+right)shr 1);
build(node*2+1,(left+right)shr 1+1,right);
end;
procedure change(node:longint);
var
mid:longint;
begin
if (left<=l[node])and(right>=r[node]) then
begin
inc(v[node],p);
inc(max[node],p);
exit;
end;
mid:=(l[node]+r[node])shr 1;
if left<=mid then change(node*2);
if right>mid then change(node*2+1);
max[node]:=max0(max[node*2],max[node*2+1])+v[node];
end;
begin
while not eoln do
begin
read(n,w,h);
if (n=0)or(w=0)or(h=0) then
begin
writeln(0);
readln;
continue;
end;
fillchar(l,sizeof(l),0);
fillchar(r,sizeof(r),0);
fillchar(max,sizeof(max),0);
fillchar(v,sizeof(v),0);
fillchar(z,sizeof(z),0);
fillchar(num,sizeof(num),0);
fillchar(nowy,sizeof(nowy),0);
fillchar(nowx,sizeof(nowx),0);
fillchar(x,sizeof(x),0);
fillchar(y,sizeof(y),0);
fillchar(other,sizeof(other),0);
for i:=1 to n do
begin
read(a,b,c);
x[i]:=a;
y[i]:=b;
z[i]:=c;
num[i]:=i;
other[i]:=i+n;
j:=i+n;
x[j]:=x[i];
y[j]:=y[i]+h;
z[j]:=-z[i];
num[j]:=j;
other[j]:=j-n;
j:=i+n*2;
x[j]:=x[i]+w;
y[j]:=y[i];
z[j]:=-z[i];
num[j]:=j;
other[j]:=j+n;
j:=i+n*3;
x[j]:=x[i]+w;
y[j]:=y[i]+h;
z[j]:=z[i];
num[j]:=j;
other[j]:=j-n;
end;
qsort1(1,4*n);
tot:=0;
for i:=1 to 4*n do
begin
if (i=1)or(x[i]<>x[i-1]) then inc(tot);
nowx[num[i]]:=tot;
end;
xx:=tot;
qsort2(1,4*n);
tot:=0;
for i:=1 to 4*n do
begin
if (i=1)or(y[i]<>y[i-1]) then inc(tot);
nowy[num[i]]:=tot
end;
yy:=tot;
qsort(1,4*n);
build(1,1,yy);
tail:=0;
ans:=0;
while tail<4*n do
begin
inc(tail);
if other[tail]>tail then
begin
left:=nowy[tail];
right:=nowy[other[tail]];
p:=z[tail];
change(1);
end;
while (tail<4*n)and(nowx[tail]=nowx[tail+1]) do
begin
inc(tail);
if other[tail]>tail then
begin
left:=nowy[tail];
right:=nowy[other[tail]];
p:=z[tail];
change(1);
end;
end;
if max[1]>ans then ans:=max[1];
end;
writeln(ans);
readln;
end;
end.
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator