Cod sursa(job #79502)

Utilizator peanutzAndrei Homorodean peanutz Data 22 august 2007 19:50:05
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>

using namespace std;

typedef struct punct
{
	int x, y;
};

#define NMAX 16010

punct p[NMAX];
int n, nr;
vector<int> a[NMAX*5];
int y[NMAX];

void read()
{
	int i;
	scanf("%d", &n);
	for(i = 1; i <= n; ++i)
		scanf("%d%d", &p[i].x, &p[i].y), y[i] = p[i].y;
}

bool comp(const punct& x, const punct& y)
{
	return (x.x < y.x || (x.x == y.x && x.y < y.y));
}

#define mid(st, dr) (((st)+(dr)) >> 1)
#define left(i) ((i) << 1)
#define right(i) (((i) << 1)+1)

int x1, y1, x2, y2, res;

int binary_search(int n)
{
	int st, dr, keep1 = 0, keep2 = 0, m;

	st = 0, dr = a[n].size()-1;

	while(st <= dr)
	{
		m = mid(st, dr);

		if(a[n][m] >= y1)
			keep1 = m, dr = m-1;
		else
			st = m+1;

		if(dr < 0)
			break;
	}

	st = 0, dr = a[n].size()-1;

	if(a[n][dr] <= y2)
		return dr-keep1+1;

	while(st <= dr)
	{
		m = mid(st, dr);

		if(a[n][m] <= y2)
			keep2 = m, st = m+1;
		else
			dr = m-1;

		if(dr < 0)
			break;
	}

	return keep2-keep1+1;
}

void query(int n, int st, int dr)
{
	if(p[st].x >= x1 && p[dr].x <= x2)
	{
		for(int i = st; i <= dr; ++i)
			if(p[i].y >= y1 && p[i].y <= y2)
				++res;

		//res += binary_search(n);
		return ;
	}

	if(st == dr)
		return ;

	int m = mid(st, dr);

	if(x1 <= p[m].x)
		query(left(n), st, m);
	if(p[m].x < x2)
		query(right(n), m+1, dr);
}


void build(int n, int st, int dr)
{
	a[n].reserve(dr-st+1);

	for(int i = st; i <= dr; ++i)
		a[n].push_back(y[i]);

	sort(a[n].begin(), a[n].end());

	if(st == dr)
		return ;

	int m = mid(st, dr);

	build(left(n), st, m);
	build(right(n), m+1, dr);
}

int main()
{
	freopen("zoo.in", "r", stdin);
	freopen("zoo.out", "w", stdout);

	read();

	sort(p+1, p+n+1, comp);

	build(1, 1, n);

	int i;
	scanf("%d", &nr);

	for(i = 1; i <= nr; ++i)
	{
		res = 0;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

		query(1, 1, n);

		printf("%d\n", res);
	}

	return 0;
}