AREA - Diện tích hình chữ nhật

Tác giả: RR

Ngôn ngữ: Pascal

uses math;
var
  res,now,n,i,x1,y1,x2,y2,m:longint;
  sl,sum:array[1..131072] of longint;
  x,u,v,typ:array[1..20111] of longint;

procedure swap(var a,b:longint);
    var
      tmp:longint;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure sort(l,r:longint);
    var
      i,j,mid:longint;
    begin
      i:=l; j:=r; mid:=x[l+random(r-l+1)];
      repeat
        while x[i]<mid do inc(i);
        while x[j]>mid do dec(j);
        if i<=j then
          begin
            swap(x[i],x[j]);
            swap(u[i],u[j]);
            swap(v[i],v[j]);
            swap(typ[i],typ[j]);
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort(i,r);
      if l<j then sort(l,j);
    end;

procedure update(u,v,k,i,l,r:longint);
    var
      mid:longint;
    begin
      if (v<l) or (r<u) then exit;
      if (u<=l) and (r<=v) then
        begin
          inc(sl[i],k);
          if sl[i]>0 then sum[i]:=r-l+1
          else sum[i]:=sum[i*2]+sum[i*2+1];
          exit;
        end;

      mid:=(l+r) shr 1;
      update(u,v,k,i*2,l,mid);
      update(u,v,k,i*2+1,mid+1,r);

      if sl[i]=0 then sum[i]:=sum[i*2]+sum[i*2+1]
      else sum[i]:=r-l+1;
    end;

begin
  read(n); m:=0;
  for i:=1 to n do
    begin
      read(x1,y1,x2,y2);
      inc(x1); inc(y1); inc(x2);
      inc(m);
        x[m]:=x1;
        u[m]:=y1;
        v[m]:=y2;
        typ[m]:=1;

      inc(m);
        x[m]:=x2;
        u[m]:=y1;
        v[m]:=y2;
        typ[m]:=-1;
    end;
  sort(1,m);

  now:=1; res:=0;
  for i:=1 to 30111 do
    begin
      while (x[now]=i) do
        begin
          update(u[now],v[now],typ[now],1,1,30111);
          inc(now);
        end;
      inc(res,sum[1]);
    end;

  writeln(res);
end.

Download