Cod sursa(job #494938)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 23 octombrie 2010 13:25:21
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.68 kb
#include <stdio.h>

#include <algorithm>
#include <vector>

using namespace std;

struct point
{
	int x, y;
};

int n, m;
point p1, p2, v[16005];
vector <int> aint[32805];

inline int cmp (point a, point b)
{
	if (a.x != b.x)
		return a.x < b.x;
	return a.y <= b.y;
}

int cautare_x (int x)
{
	int st = 0, dr = n + 1, m, sol;
	
	while (st <= dr)
	{
		m = (st + dr) >> 1;
		if (v[m].x >= x)
		{
			dr = m - 1;
			sol = m;
		}
		else
			st = m + 1;
	}
	return sol;
}

int cautare_y (int y, int ind)
{
	int st = 0, dr = aint[ind].size () - 1, m, sol = dr;
	
	while (st <= dr)
	{
		m = (st + dr) >> 1;
		if (aint[ind][m] >= y)
		{
			dr = m - 1;
			sol = m;
		}
		else
			st = m + 1;
	}
	return sol;
}

void build (int nod, int st, int dr)
{
	if (st == dr)
	{
		aint[nod].push_back (v[st].y);
		return;
	}
	
	int m = (st + dr) >> 1, fiust = nod * 2, fiudr = nod * 2 + 1, i, j;
	
	build (fiust, st, m);
	build (fiudr, m + 1, dr);
	
	i = j = 0;
	while (i < aint[fiust].size() && j < aint[fiudr].size())
		if (aint[fiust][i] <= aint[fiudr][j])
			aint[nod].push_back (aint[fiust][i ++]);
		else
			aint[nod].push_back (aint[fiudr][j ++]);
	while (i < aint[fiust].size())
		aint[nod].push_back (aint[fiust][i ++]);
	while (j < aint[fiudr].size())
		aint[nod].push_back (aint[fiudr][j ++]);
}

int query (int nod, int st, int dr, int left, int right)
{
	if (left <= st && dr <= right)
	{
		if (p1.y <= aint[nod][0])
			st = 0;
		else
			st = cautare_y (p1.y, nod);
		if (aint[nod][aint[nod].size() - 2] <= p2.y)
			dr = aint[nod].size() - 2;
		else
			dr = cautare_y (p2.y + 1, nod);
		if (aint[nod][dr] > p2.y)
			dr --;
		if (st > dr)
			return 0;
		return dr - st + 1;
	}
	
	int m = (st + dr) >> 1, s = 0;
	if (left <= m)
		s = s + query (nod * 2, st, m, left, right);
	if (m < right)
		s = s + query (nod * 2 + 1, m + 1, dr, left, right);
	return s;
}

int main ()
{
	freopen ("zoo.in", "r", stdin);
	freopen ("zoo.out", "w", stdout);
	
	scanf ("%d", &n);
	
	int i, st, dr;
	
	for (i = 1; i <= n; i ++)
		scanf ("%d %d", &v[i].x, &v[i].y);
	v[0].x = v[0].y = -2000000001;
	v[n + 1].x = v[n + 1].y = 2000000001;
	
	for (i = 1; i < n; i ++)
		if (cmp (v[i], v[i + 1]) == 0)
		{
			sort (v + 1, v + n + 1, cmp);
			break;
		}
	build (1, 1, n);
	for (i = 1; i <= 32800; i ++)
		aint[i].push_back (2000000001);
	
	scanf ("%d", &m);
	for (i = 1; i <= m; i ++)
	{
		scanf ("%d %d %d %d", &p1.x, &p1.y, &p2.x, &p2.y);
		st = cautare_x (p1.x);
		dr = cautare_x (p2.x + 1);
		if (v[dr].x > p2.x)
			dr --;
		if (st > dr)
			printf ("0\n");
		else
			printf ("%d\n", query (1, 1, n, st, dr));
	}
	return 0;
}