现在的位置: 首页 > 算法 > 正文

poj1389——by rfy

2018年05月02日 算法 ⁄ 共 2424字 ⁄ 字号 评论关闭
type
tree=record
l,r,v,fl:int64;
end;
bian=record
x,y1,y2,pd:int64;
end;
var
x,y,xx,yy,num,ans,max:int64;
i:longint;
t:array[1..1000000] of tree;
b:array[1..1000000] of bian;

function maxn(a,b:int64):int64;
begin
if a>b then
  exit(a)
else exit(b);
end;

procedure sort(l,r: int64);
      var
         i,j,x,y: int64;
      begin
         i:=l;
         j:=r;
         x:=b[(l+r) div 2].x;
         repeat
           while b[i].x<x do
            inc(i);
           while x<b[j].x do
            dec(j);
           if not(i>j) then
             begin
                y:=b[i].x;
                b[i].x:=b[j].x;
                b[j].x:=y;
                y:=b[i].y1;
                b[i].y1:=b[j].y1;
                b[j].y1:=y;
                y:=b[i].y2;
                b[i].y2:=b[j].y2;
                b[j].y2:=y;
                y:=b[i].pd;
                b[i].pd:=b[j].pd;
                b[j].pd:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;

procedure build(p,x,y:int64);
begin
t[p].l:=x;
t[p].r:=y;
t[p].v:=0;
t[p].fl:=0;
if x<>y then
begin
  build(p*2,x,(x+y) div 2);
  build(p*2+1,(x+y) div 2+1,y);
end;
end;

procedure wh(p:int64);
begin
if t[p].l=t[p].r then
begin
  if t[p].v=0 then
    t[p].fl:=0
  else t[p].fl:=1;
  exit;
end;
if t[p].v>0 then
begin
  t[p].fl:=1;
  exit;
end;
if (t[p*2].fl=1)and(t[p*2+1].fl=1) then
begin
  t[p].fl:=1;
  exit;
end;
if (t[p*2].fl=0)and(t[p*2+1].fl=0) then
begin
  t[p].fl:=0;
  exit;
end;
t[p].fl:=-1;
end;

procedure insert(p,x,y:int64);
var mid:int64;
begin
if x>y then
  exit;
if (t[p].l=x)and(t[p].r=y) then
begin
  inc(t[p].v);
  wh(p);
  exit;
end;
mid:=(t[p].l+t[p].r) div 2;
if y<=mid then
begin
  insert(p*2,x,y);
  wh(p);
  exit;
end;
if x>mid then
begin
  insert(p*2+1,x,y);
  wh(p);
  exit;
end;
insert(p*2,x,mid);
insert(p*2+1,mid+1,y);
wh(p);
end;

procedure delete(p,x,y:int64);
var mid:int64;
begin
if x>y then
  exit;
if (t[p].l=x)and(t[p].r=y) then
begin
  dec(t[p].v);
  wh(p);
  exit;
end;
mid:=(t[p].l+t[p].r) div 2;
if y<=mid then
begin
  delete(p*2,x,y);
  wh(p);
  exit;
end;
if x>mid then
begin
  delete(p*2+1,x,y);
  wh(p);
  exit;
end;
delete(p*2,x,mid);
delete(p*2+1,mid+1,y);
wh(p);
end;

function sum(p:int64):int64;
var mid:int64;
begin
if t[p].fl=0 then
  exit(0);
if t[p].fl=1 then
  exit(t[p].r-t[p].l+1);
exit(sum(p*2)+sum(p*2+1));
end;


begin
while true do
begin
  num:=0;
  max:=0;
  readln(x,y,xx,yy);
  if x=-1 then
    break;
  inc(x);
  inc(xx);
  inc(y);
  inc(yy);
  inc(num);
  b[num].x:=x;
  b[num].y1:=y;
  b[num].y2:=yy;
  b[num].pd:=0;
  inc(num);
  b[num].x:=xx;
  b[num].y1:=y;
  b[num].y2:=yy;
  b[num].pd:=1;
  if yy>max then
    max:=yy;
  while true do
  begin
    readln(x,y,xx,yy);
    if x=-1 then
      break;
    inc(x);
    inc(xx);
    inc(y);
    inc(yy);
    if yy>max then
      max:=yy;
    inc(num);
    b[num].x:=x;
    b[num].y1:=y;
    b[num].y2:=yy;
    b[num].pd:=0;
    inc(num);
    b[num].x:=xx;
    b[num].y1:=y;
    b[num].y2:=yy;
    b[num].pd:=1;
  end;
  sort(1,num);
  max:=max*2;
  build(1,1,max);
  ans:=0;
  for i:=1 to num do
  begin
    if i<>1 then
      ans:=ans+maxn((sum(1)),0)*(b[i].x-b[i-1].x);
    if b[i].pd=0 then
      insert(1,b[i].y1+1,b[i].y2)
    else delete(1,b[i].y1+1,b[i].y2);
  end;
  writeln(ans);
end;
end.

抱歉!评论已关闭.