Cod sursa(job #631590)

Utilizator floringh06Florin Ghesu floringh06 Data 8 noiembrie 2011 20:21:02
Problema Zoo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.13 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

#define FIN "zoo.in"
#define FOUT "zoo.out"
#define MAX_N 16005
#define x first
#define y second
#define pb push_back
#define INF 2000000005

vector <int> A[MAX_N * 4];
pair <int, int> P[MAX_N];

int N, M, RES;
int x1, x2, y1, y2;

     void merge (int nod, int li, int lf)
     {
          int sl = (nod << 1);
          int sr = (nod << 1)|1;
          
          // santinele
          A[sl].pb(INF), A[sr].pb (INF);
          
          int i, j, k;
          for (i = 0, j = 0, k = 0; k <= lf - li; ++k)
              if (A[sl][i] < A[sr][j]) A[nod].pb(A[sl][i++]);
                                  else A[nod].pb(A[sr][j++]);
     }

     void buildtree (int nod, int li, int lf)
     {
          if (li == lf) A[nod].pb (P[li].y);
          else 
               {
                    int m = (li + lf) >> 1;
                    buildtree (nod << 1, li, m);
                    buildtree ((nod << 1)|1, m + 1, lf);
                    
                    merge (nod, li, lf);
               }
     }
     
     int binar (int nod, int y1, int y2)
     {
          int m, li, lf, cnt_y1, cnt_y2;
          if (A[nod][0] > y2) return 0;
          if (A[nod][A[nod].size() - 1] < y1) return 0;
          
          li = 0, lf = A[nod].size() - 1;
          
          while (li <= lf)
          {
                m = (li + lf) >> 1;
                if (A[nod][m] < y1) li = m + 1;
                   else lf = m - 1;
          }
          while (A[nod][m - 1] >= y1 && m) --m;
          while (A[nod][m] < y1 && m < A[nod].size() - 1) ++m;
          cnt_y1 = m;
          
          li = 0, lf = A[nod].size() - 1;
          
          while (li <= lf)
          {
                m = (li + lf) >> 1;
                if (A[nod][m] < y2) li = m + 1;
                   else lf = m - 1;
          }
          while (A[nod][m + 1] <= y2 && m < A[nod].size() - 1) ++m;
          while (A[nod][m] > y2 && m) --m;
          cnt_y2 = m;
          
          return cnt_y2 - cnt_y1 + 1;
     }
     
     void query (int nod, int li, int lf)
     {
          if (x1 <= P[li].x && P[lf].x <= x2)
          {
                 // cautari binare
                 RES += binar (nod, y1, y2);
          }
          else if (li != lf)
              {
                    int m = (li + lf) >> 1;
                    if (x1 <= P[m].x) query (nod << 1, li, m);
                    if (P[m + 1].x <= x2) query ((nod << 1)|1, m + 1, lf);
              }
     }

     int main ()
     {
         int i;
         freopen (FIN, "r", stdin);
         freopen (FOUT, "w", stdout);
         
         scanf ("%d", &N);
         for (i = 1; i <= N; ++i) scanf ("%d %d", &P[i].x, &P[i].y);
         sort (P + 1, P + N + 1);
         buildtree (1, 1, N);
         scanf ("%d", &M);
         while (M--)
         {
               scanf ("%d %d %d %d", &x1, &y1, &x2, &y2);
               RES = 0;
               query (1, 1, N);
               printf ("%d\n", RES);
         }
         
         return 0;
     }