Cod sursa(job #507716)

Utilizator APOCALYPTODragos APOCALYPTO Data 6 decembrie 2010 17:14:58
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb
using namespace std;
#include<cstdio>
#include<fstream>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#define nmax 16005
#define common int m=(l+r)/2, L=2*n, R=L|1
struct nod{
int x,y;};
nod a[nmax];
int N,M,x1,x2,y1,y2;;
int *H[3*nmax],len[3*nmax];
ofstream fout("zoo.out");

struct cmp{
  bool operator()(const nod &i,const nod &j)const
  {
      return i.x<j.x;
  }
};

void build(int n,int l,int r)
{
    if(l>=r)
    {
        H[n]=new int[3];
        H[n][len[n]++]=a[l].y;
        return;
    }
    common;

    build(L,l,m);
    build(R,m+1,r);

    int NL=len[L], NR=len[R], i, j;

    H[n]=new int[NL+NR+3];

    for(i=0,j=0; i<NL && j<NR; )
        if(H[L][i]<=H[R][j]) H[n][len[n]++]=H[L][i++];
        else H[n][len[n]++]=H[R][j++];

    for(; i<NL; ) H[n][len[n]++]=H[L][i++];
    for(; j<NR; ) H[n][len[n]++]=H[R][j++];

}

inline int bsearch(int a[], int n, int l, int r)
{
    int i,cnt;
    int p=0, q=0;

    for(i=0,cnt=(1<<15);cnt; cnt/=2)
    {
        if(i+cnt<=n)
          if(a[i+cnt-1]<=r)
           i+=cnt;
    }
    q=i;

    for(i=n+1,cnt=(1<<15);cnt;cnt/=2)
    {
        if(i-cnt>=1)
          if(a[i-cnt-1]>=l)
           i-=cnt;

    }
    p=i;
    return q-p+1;
}

inline int query(int n,int ql,int qr,int l,int r)
{
     if(ql<=l && r<=qr)
     {
         if(y2<H[n][0] || y1>H[n][len[n]-1]) return 0;

         if(y1<=H[n][0] && H[n][len[n]-1] <= y2) return (r-l+1);
         return bsearch(H[n],len[n],y1,y2);
     }

     common;

     int s=0;

     if(ql<=m) s+=query(L,ql,qr,l,m);
     if(qr>m)  s+=query(R,ql,qr,m+1,r);

     return s;


}

void cit()
{int i,cnt;
    ifstream fin("zoo.in");
    fin>>N;


    for(i=1;i<=N;i++)
    {
        fin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+N+1,cmp());

    build(1,1,N);

    fin>>M;
    for(i=1;i<=M;i++)
    {
        fin>>x1>>y1>>x2>>y2;
        if(x2<a[1].x || x1>a[N].x) {fout<<"0\n";}
        else
        {
           for(i=0,cnt=1<<15;cnt;cnt/=2)
           {
               if(i+cnt<=N)
               {
                   if(a[i+cnt].x<=x2)
                     i+=cnt;
               }
           }
           x2=i;
           for(i=N+1,cnt=1<<15;cnt;cnt/=2)
           {
               if(i-cnt>=1)
                 if(a[i-cnt].x>=x1)
                     i-=cnt;

           }
           x1=i;
           fout<<query(1,x1,x2,1,N)<<"\n";
        }
    }
    fin.close();
}

int main()
{
     cit();
    fout.close();
    return 0;
}