Cod sursa(job #55720)

Utilizator astronomyAirinei Adrian astronomy Data 28 aprilie 2007 11:34:55
Problema Zoo Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <stdio.h>
#include <stdlib.h>

#define MAXN (1 << 15)
#define LOGN 16

typedef struct point
{
	int x, y;
}
point;

int N, M, x1, x2, y10, y2;
int X[MAXN], T[LOGN][MAXN];

point P[MAXN];

void build(int nod, int lv, int st, int dr)
{
	int i, j, k, mij = (st + dr) >> 1;
	if(st > dr) return ;
	if(st == dr) T[lv][st] = P[st].y;
	else
	{
		build(2*nod, lv+1, st, mij), build(2*nod+1, lv+1, mij+1, dr);
		for(i = st, j = mij+1, k = st; k <= dr;)
			if(i > mij || (T[lv+1][j] < T[lv+1][i] && j <= dr))
				T[lv][k++] = T[lv+1][j++];
			else
				T[lv][k++] = T[lv+1][i++];
	}
}

int search(int A[], int st, int dr, int v);

int query(int nod, int lv, int st, int dr)
{
	int mij = (st + dr) >> 1, t = 0;
	if(x1 <= st && dr <= x2)
	{
		if(y2 < T[lv][st] || y10 > T[lv][dr])
			return 0;
		return search(T[lv], st, dr, y2) - search(T[lv], st, dr, y10-1);
	}
	else
	{
		if(x1 <= mij)
			t += query(2*nod, lv+1, st, mij);
		if(x2 > mij)
			t += query(2*nod+1, lv+1, mij+1, dr);
		return t;
	}
}
int search(int A[], int st, int dr, int v)
{
	int l = st, r = dr, m, val;
	if(A[st] > v) return st-1;
	if(A[dr] < v) return dr;
	while(l <= r)
	{
		m = (l + r) >> 1;
		if(v < A[m]) r = m-1;
		else val = m, l = m+1;
	}
	return val;
}
int cmp(const void *a, const void *b)
{
	if( ((point *)a)->x != ((point *)b)->x )
		return ((point *)a)->x - ((point *)b)->x;
	return ((point *)a)->y - ((point *)b)->y;
}
void read_and_solve(void)
{
	int i, j, u;

	scanf("%d\n", &N);

	for(i = 0; i < N; i++)
		scanf("%d %d\n", &P[i].x, &P[i].y);

	qsort(P, N, sizeof(P[0]), cmp);

	for(i = 0; i < N; i++)
		X[i] = P[i].x;

	build(1, 0, 0, N-1);

	scanf("%d", &M);

	for(i = 1; i <= M; i++)
	{
		scanf("%d %d %d %d", &x1, &y10, &x2, &y2);
		if(x1 > X[N-1] || x2 < X[0])
		{
			printf("0\n");
			continue;
		}
		x1 = search(X, 0, N-1, x1-1) + 1, x2 = search(X, 0, N-1, x2);
		printf("%d\n", query(1, 0, 0, N-1));
	}
}
int main(void)
{
	freopen("zoo.in", "rt", stdin);
	freopen("zoo.out", "wt", stdout);

	read_and_solve();

	return 0;
}