# Cod sursa(job #285733)

Utilizator Data 22 martie 2009 21:27:01 Zoo 100 cpp done Arhiva de probleme 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;
}
``````