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 cas_shmily at 2011-04-01 20:09:45 on Problem 2482
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:
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