Cod sursa(job #92312)

Utilizator VmanDuta Vlad Vman Data 14 octombrie 2007 22:01:51
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.99 kb
using namespace std;
#include <stdio.h>
#include <vector>

#define Nmax 16005

struct nod { 
            int nr;
            vector<int> listy;
           };
nod a[3*Nmax+10];
int N,M,i,tot;
int x[Nmax],y[Nmax],xs,ys,xf,yf;

inline void swap(int &a,int &b)
{
 int aux=a;a=b;b=aux;
}

void qsort(int st,int dr)
{
     int i,j,m;
     i=st;j=dr;m=x[(st+dr)>>1];
     while (i<=j)
           {
                 while (x[i]<m) ++i;
                 while (m<x[j]) --j;
                 if (i<=j)
                    {
                     swap(x[i],x[j]);
                     swap(y[i],y[j]);
                     ++i;--j;                          
                    }
           }
 if (i<dr) qsort(i,dr);
 if (st<j) qsort(st,j);
}

void update(int poz,int li,int ls,int nod)
{
     int i,j,m=(li+ls)>>1;
     if (li==ls)
        {
         ++a[nod].nr;
         a[nod].listy.push_back(y[poz]);                
         return;
        }
     a[nod].nr=1;
     if (poz<=m) update(poz,li,m,nod<<1);
        else if (poz>m) update(poz,m+1,ls,(nod<<1)+1);
     //interclasare
}

void interclasare(int nod)
{
     int i,j,x1,x2,nr1,nr2;
     if (a[nod<<1].nr>0) interclasare(nod<<1);
     if (a[(nod<<1)+1].nr>0) interclasare((nod<<1)+1);
     nr1=a[nod<<1].nr;
     nr2=a[(nod<<1)+1].nr;
     i=j=0;
     while ((i<nr1) && (j<nr2))
           {
            x1=a[nod<<1].listy[i];
            x2=a[(nod<<1)+1].listy[j];
            if (x1<x2) { a[nod].listy.push_back(x1);++i; }
               else { a[nod].listy.push_back(x2);++j; }
           }
    for (;i<nr1;++i)
        a[nod].listy.push_back(a[nod<<1].listy[i]);
    for (;j<nr2;++j)
        a[nod].listy.push_back(a[(nod<<1)+1].listy[j]);
    a[nod].nr=a[nod].listy.size();
}

int cautaYmic(int nod,int yy)
{
 int p=1,rez=0;
 while ((p<<1)<=a[nod].nr) p<<=1;
 while (p)
	{
	 if (yy>y[a[nod].listy[rez+p-1]]) rez+=p;
	 p>>=1;
	 while (rez+p>a[nod].nr) p>>=1;
	}
 return rez;
}

int cautaYmare(int nod,int yy)
{
 int p=1,rez=0;
 while ((p<<1)<=a[nod].nr) p<<=1;
 while (p)
	{
	 if (yy>=y[a[nod].listy[rez+p-1]]) rez+=p;
	 p>>=1;
	 while (rez+p>a[nod].nr) p>>=1;
	}
 return rez;
}

void query(int li,int ls,int nod)
{
 int m=(li+ls)>>1;
 if ((xs<=x[li])&&(xf>=x[ls]))
	{
	 tot=tot+cautaYmare(nod,yf)-cautaYmic(nod,ys);
	 return;
	}
 if (xs<=x[m])
	if (xf<=x[m]) query(li,m,nod<<1);
		else {
			query(li,m,nod<<1);query(m+1,ls,(nod<<1)+1); }
    else query(m+1,ls,(nod<<1)+1);
}

int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    scanf("%d",&N);
    for (i=1;i<=N;++i)
         scanf("%d %d",&x[i],&y[i]);
    qsort(1,N);
    for (i=1;i<=N;++i)
        update(i,1,N,1);
    interclasare(1);
    scanf("%d",&M);
    for (i=0;i<M;++i)
        {
         scanf("%d %d %d %d",&xs,&ys,&xf,&yf);
		 tot=0;
         query(1,N,1);
		 printf("%d\n",tot);
        }    
    fclose(stdout);
    fclose(stdin);
    return 0;                           
}