Cod sursa(job #216834)

Utilizator zombie_testertest test zombie_tester Data 25 octombrie 2008 22:44:58
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.1 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);
         
         
         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 = 0;
         
         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);
               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",?,&yi);
              scanf("%d%d",&xf,&yf);
              
              rez = 0;
              query(1,0,N-1);
              
              printf("%d\n",rez);
           }
         
         return 0;
     }