Cod sursa(job #597667)

Utilizator mathboyDragos-Alin Rotaru mathboy Data 22 iunie 2011 19:59:49
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <cstdio>
#include <algorithm>
#include <vector>

#define MAXN 16010
#define MAXARB 4 * MAXN
#define getcommon int m = (l + r) >> 1, L = m << 1, R = L | 1
#define x first
#define y second
using namespace std;

pair <int, int> A[MAXN];

int len[MAXARB], *lst[MAXARB];
int B[MAXN], N, M;


void build_tree(int n, int l, int r) {
	
	lst[n] = new int[r - l + 2];
	len[n] = r - l + 1;

	if(l == r) {
		lst[n][1] = A[l].y;
		return ;
	}
	getcommon;
	
	build_tree(L, l, m);
	build_tree(R, m + 1, r);

	int i = 1, j = 1, p = 0;
	
	for(; i <= len[L] && j <= len[R]; ) {
		if(lst[L][i] < lst[R][j])
			lst[n][++p] = lst[L][i++];
		else lst[n][++p] = lst[R][j++];
	}
	for(; i <= len[L]; i++)
		lst[n][++p] = lst[L][i];
	for(; j <= len[R]; j++)
		lst[n][++p] = lst[R][j];
}

int res;

inline int cbinLow2(int A[], int l, int r, int val) {
	int s = N + 1, m;
	for(; l <= r; ) {
		m = l + (r - l) / 2;
		if(A[m] >= val) {
			s = m;
			r = m - 1;
		} else l = m + 1;
	}
	return s;
}
inline int cbinHigh2(int A[], int l, int r, int val) {
	int s = 0, m;
	for(; l <= r; ) {
		m = l + (r - l) / 2;
		if(A[m] <= val) {
			s = m;
			l = m + 1;
		} else r = m - 1;
	}
	return s;
}

void query_tree(int n, int l, int r, int a, int b, int y1, int y2) {
	if (a <= l && b >= r) {
		int p1, p2;
		p1 = cbinLow2(lst[n], 1, len[n], y1);
		p2 = cbinHigh2(lst[n], 1, len[n], y2);
		
		if(p1 <= p2)
			res += p2 - p1 + 1;
		return ;
	}
	getcommon;
	
	if(a <= m) query_tree(L, l, m, a, b, y1, y2);
	if(b > m) query_tree(R, m + 1, r, a, b, y1, y2);
}
inline int cbinlow1(pair <int, int> A[], int l, int r, int val) {
	
	int s = N + 1, m;
	for(; l <= r; ) {
		m = l + (r - l) / 2;
		if(A[m].x >= val) {
			s = m;
			r = m - 1;
		} else l = m + 1;
	}
	return s;
}
inline int cbinhigh1(pair <int, int> A[], int l, int r, int val) {
	int s = 0, m;
	for(; l <= r; ) {
		m = l + (r - l) / 2;
		if(A[m].x <= val) {
			s = m;
			l = m + 1;
		} else r = m - 1;
	}
	return s;
}
int main() {

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

	scanf("%d\n", &N);
	
	int i, x1, x2, y1, y2, p1, p2;

	for(i = 1; i <= N; i++)
		scanf("%d %d\n", &A[i].x, &A[i].y);
	
	sort(A + 1, A + N + 1);
#ifdef DEBUB	
	for(i = 1; i <= N; i++) {
		printf("%d ", A[i].x);
	}
	printf("\n");
#endif
	build_tree(1, 1, N);
	
	for(scanf("%d\n", &M); M--; ) {
		scanf("%d %d %d %d\n", &x1, &y1, &x2, &y2);
		
		res = 0;

		p1 = cbinlow1(A, 1, N, x1);
		p2 = cbinhigh1(A, 1, N, x2);
	
//		printf("(%d) -> %d, (%d) -> %d\n", x1, p1, x2, p2);
		if(p1 <= p2)
			query_tree(1, 1, N, p1, p2, y1, y2);
		printf("%d\n", res);
	}
	return 0;
}