Cod sursa(job #85027)

Utilizator CezarMocanCezar Mocan CezarMocan Data 19 septembrie 2007 17:49:20
Problema Zoo Scor 30
Compilator fpc Status done
Runda Arhiva de probleme Marime 2.48 kb
type animal=record
                x,y:longint;
                end;
var v:array[0..16001]of animal;
    a,b,n,m,i,j,p1,p2,c,d:longint;
    aux:animal;

procedure qsort(s,d:longint);
var aux:animal;
    i,j:longint;
begin
i:=s;
j:=d;
while true do
        begin
        while ((v[i].x<v[j].x)or((v[i].x=v[j].x)and(v[i].y<=v[j].y)))and(i<>j) do inc(i);
        if i=j then
                break;
        aux:=v[i];v[i]:=v[j];v[j]:=aux;dec(j);
        while ((v[i].x<v[j].x)or((v[i].x=v[j].x)and(v[i].y<=v[j].y)))and(i<>j) do dec(j);
        if i=j then
                break;
        aux:=v[i];v[i]:=v[j];v[j]:=aux;inc(i);
        end;
if i+1<d then
        qsort(i+1,d);
if j-1>s then
        qsort(s,j-1);
end;

function posibil_jos(p:animal):boolean;
begin
if (p.x>=a)and(p.y>=b) then
        posibil_jos:=true
else
        posibil_jos:=false;
end;

function cauta_jos(l,r:longint):longint;
var m:longint;
begin
m:=(l+r) div 2;
if posibil_jos(v[m])and((not posibil_jos(v[m-1]))or(m-1=0)) then
        begin
        cauta_jos:=m;
        exit;
        end;
if l>=r then
        begin
        cauta_jos:=0;
        exit;
        end;
if posibil_jos(v[m]) then
        cauta_jos:=cauta_jos(l,m-1)
else
        cauta_jos:=cauta_jos(m+1,r);
end;

/////////////***********************\\\\\\\\\\\\\

function posibil_sus(p:animal):boolean;
begin
if (p.x<=c)and(p.y<=d) then
        posibil_sus:=true
else
        posibil_sus:=false;
end;

function cauta_sus(l,r:longint):longint;
var m:longint;
begin
m:=(l+r) div 2;
if posibil_sus(v[m])and((not posibil_sus(v[m+1]))or(m+1>n)) then
        begin
        cauta_sus:=m;
        exit;
        end;
if l>=r then
        begin
        cauta_sus:=0;
        exit;
        end;
if posibil_sus(v[m]) then
        cauta_sus:=cauta_sus(m+1,r)
else
        cauta_sus:=cauta_sus(l,m-1);
end;


begin
assign(input,'zoo.in');reset(input);
assign(output,'zoo.out');rewrite(output);
readln(n);
for i:=1 to n do
        readln(v[i].x,v[i].y);
randomize;
for i:=1 to n do
        begin
        p1:=random(n)+1;
        p2:=random(n)+1;
        aux:=v[p1];
        v[p1]:=v[p2];
        v[p2]:=aux;
        end;
qsort(1,n);
readln(m);
for i:=1 to m do
        begin
        readln(a,b,c,d);
        p1:=cauta_jos(1,n);
        p2:=cauta_sus(1,n);
        if (p1=0)or(p2=0) then
                writeln(0)
        else
                writeln(p2-p1+1);
        end;
close(input);close(output);
end.