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