Cod sursa(job #253254)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 16:42:17
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.54 kb
 # include <cstdio>  
 # include <vector>  
 # include <algorithm>  
   
 using namespace std;  
   
 # define FIN "zoo.in"  
 # define FOUT "zoo.out"  
 # define max 2000000000  
 # define pb push_back  
 # define f first  
 # define s second  
 # define MAXN 1 << 14  
 # define MAXK 1 << 15  
   
 int N,M,i,j,xi,yi,xf,yf,rez;  
 pair <int, int> P[MAXN];  
 vector <int> A[MAXK];  
   
      void Interclas(int nod,int st,int dr)  
      {  
          int mij, m, n, rh, lf, i;  
            
          lf = nod << 1; rh = lf | 1;  
            
          A[lf].pb(max+1);  
          A[rh].pb(max+1);  
            
          mij = dr - st;  
          n = m = 0;  
            
          for (i = 0; i <= mij; ++i)  
            if (A[lf][n] < A[rh][m])  
              A[nod].pb(A[lf][n++]);  
            else  
              A[nod].pb(A[rh][m++]);  
      }  
   
      void build(int nod, int st, int dr)  
      {  
          int mij;  
            
          if (st == dr)  
             A[nod].pb(P[st].s);  
          else  
            {  
               mij = (st + dr) >> 1;  
                 
               build(nod << 1,st,mij);  
               build(nod << 1 | 1,mij+1,dr);  
                 
               Interclas(nod, st, dr);  
            }  
      }  
        
      int LowSearch(int nod,int st,int dr,int val)  
      {  
          int mij, sol = -1;  
            
          while (st <= dr)  
            {  
                mij = (st + dr) >> 1;  
                if (val <= A[nod][mij])  
                  {  
                     sol = mij;  
                     dr = mij - 1;  
                  }  
                else st = mij + 1;  
            }  
          return sol;  
      }  
        
      int UpSearch(int nod,int st,int dr,int val)  
      {  
          int mij, sol = -1;  
            
          while (st <= dr)  
            {  
                mij = (st + dr) >> 1;  
                if (val >= A[nod][mij])  
                  {  
                      sol = mij;  
                      st = mij + 1;  
                  }  
                else dr = mij - 1;  
            }  
          return sol;  
      }  
        
      void query(int nod,int st,int dr)  
      {  
          int mij, Lx, Ly;  
            
          if (P[st].f >= xi && xf >= P[dr].f)  
            {  
                Ly = LowSearch(nod,0,dr-st,yi);  
                Lx = UpSearch(nod,0,dr-st,yf);  
                if (Ly != -1 && Lx != -1) rez += Lx - Ly + 1;  
            }  
          else  
          if (st != dr)  
            {  
                mij = (st + dr) >> 1;  
                if (xi <= P[mij].f)  
                  query(nod << 1,st,mij);  
                if (P[mij+1].f <= xf)  
                  query(nod << 1 | 1,mij+1,dr);  
            }  
      }  
   
      int main()  
      {  
          freopen(FIN,"r",stdin);  
          freopen(FOUT,"w",stdout);  
            
          scanf("%d",&N);  
          for (i = 0; i < N; ++i)  
            scanf("%d%d",&P[i].f,&P[i].s);  
            
          sort(P, P+N);  
            
          build(1,0,N-1);  
            
          scanf("%d",&M);  
          for (i = 1; i <= M; ++i)  
            {  
               scanf("%d%d",&xi,&yi);  
               scanf("%d%d",&xf,&yf);  
                 
               rez = 0;  
               query(1,0,N-1);  
                 
               printf("%d\n",rez);  
            }  
            
          return 0;  
}