Cod sursa(job #102274)

Utilizator johnyJohny Deep johny Data 14 noiembrie 2007 10:27:32
Problema Zoo Scor 20
Compilator fpc Status done
Runda Arhiva de probleme Marime 3.06 kb
const nmax=16000;
var x,y,xx,yy:array[1..nmax] of longint;
    tree:array[1..nmax,1..40] of longint;
    n,i,m:longint;
    a1,a2,a3,a4:longint;
    f,fo:text;

Procedure ms(st,dr:longint);
var i,j,k,m:longint;
begin
if st=dr
then exit;
m:=(st+dr) shr 1;
i:=st;
j:=m+1;
k:=st;
while (i<m+1) and (j<dr+1) do
      if (x[i]<x[j]) or ((x[i]=x[j]) and (y[i]<y[j]))
      then begin
           xx[k]:=x[i];
           yy[k]:=y[i];
           inc(i);
           inc(k);
           end
      else begin
           xx[k]:=x[j];
           yy[k]:=y[j];
           inc(j);
           inc(k);
           end;
while i<m+1 do
      begin
      xx[k]:=x[i];
      yy[k]:=y[i];
      inc(i);
      inc(k);
      end;
while j<dr+1 do
      begin
      xx[k]:=x[j];
      yy[k]:=y[j];
      inc(j);
      inc(k);
      end;
for i:=st to dr do
    begin
    x[i]:=xx[i];
    y[i]:=yy[i];
    end;
end;

Procedure build(niv,st,dr:longint);
var m,i,j,k:longint;
begin
if st=dr
then tree[niv,st]:=y[st]
else begin
     m:=(st+dr) shr 1;
     build(niv+1,st,m);
     build(niv+1,m+1,dr);
     i:=st;
     j:=m+1;
     k:=st;
     while (i<m+1) and (j<dr+1) do
           if tree[niv+1,i]<tree[niv+1,j]
           then begin
                tree[niv,k]:=tree[niv+1,i];
                inc(i);
                inc(k);
                end
           else begin
                tree[niv,k]:=tree[niv+1,j];
                inc(j);
                inc(k);
                end;
     while i<m+1 do
           begin
           tree[niv,k]:=tree[niv+1,i];
           inc(i);
           inc(k);
           end;
     while j<dr+1 do
           begin
           tree[niv,k]:=tree[niv+1,j];
           inc(j);
           inc(k);
           end;
     end;
end;

Function search(x1,y1,x2,y2,st,dr,niv:longint):longint;
var m,rez,bmax,q,pmax,pmin,b:longint;
begin
if (x1<=x[st]) and (x[dr]<=x2)
then begin
     q:=dr-st;
     bmax:=1;
     while bmax<q do
           bmax:=bmax shl 1;
     pmax:=st;
     pmin:=st;
     b:=bmax;
     while b>0 do
           begin
           if (pmin+b<dr+1) and (tree[niv,pmin+1]<y1)
           then pmin:=pmin+b;
           b:=b shr 1;
           end;
     b:=bmax;
     while b>0 do
           begin
           if (pmax+b<dr+1) and (tree[niv,pmax+1]<y2+1)
           then pmax:=pmax+b;
           b:=b shr 1;
           end;
     if tree[niv,pmin]>=y1
     then dec(pmin);
     search:=pmax-pmin;
     end
else begin
     rez:=0;
     m:=(st+dr) shr 1;
     if st<>dr
     then begin
          if x1<=x[m]
          then rez:=rez+search(x1,y1,x2,y2,st,m,niv+1);
          if x[m]<=x2
          then rez:=rez+search(x1,y1,x2,y2,m+1,dr,niv+1);
          end;
     search:=rez;
     end;
end;

begin
assign(f,'zoo.in');
reset(f);
readln(f,n);
for i:=1 to n do
    readln(f,x[i],y[i]);
ms(1,n);
build(1,1,n);
readln(f,m);
assign(fo,'zoo.out');
rewrite(fo);
for i:=1 to m do
    begin
    readln(f,a1,a2,a3,a4);
    writeln(fo,search(a1,a2,a3,a4,1,n,1));
    end;
close(f);
close(fo);
end.