Cod sursa(job #159351)

Utilizator city_guy91alex isip city_guy91 Data 14 martie 2008 08:24:36
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.42 kb
using namespace std;   
#include <stdio.h>   
#include <vector>   
  
#define Nmax 16005   
  
struct nod {    
            int nr;   
            vector<int> listy;   
           };   
nod a[16*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 m=(li+ls)>>1;   
     if (li==ls)   
        {   
         a[nod].nr=1;   
         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);   
}   
  
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>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>=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 (li==ls) return;   
 if (xs<=x[m])   
    {   
     if (xf>=x[m]) { query(li,m,(nod<<1));query(m+1,ls,(nod<<1)+1); }   
        else if (xf<x[m]) query(li,m,nod<<1);   
    }   
    else query(m+1,ls,(nod<<1)+1);   
}   
  
int main()   
{   
    freopen("zoo.in","r",stdin);   
    freopen("zoo.out","w",stdout);   
    scanf("%d",&N);   
    N+=2;   
    x[1]=-2000000001;   
    x[N]=2000000001;   
    for (i=2;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;   
         if ((xf>=x[1])&&(xs<=x[N])) query(1,N,1);   
         printf("%d\n",tot);   
        }       
    fclose(stdout);   
    fclose(stdin);   
    return 0;                              
}