Cod sursa(job #216904)

Utilizator alex_mircescuAlex Mircescu alex_mircescu Data 26 octombrie 2008 09:45:32
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <stdio.h>
#include <algorithm>

#define MAXN 32000
#define POW ((st + dr) >> 1)

using namespace std;

struct NODZ {
	long x, y;
};

NODZ P[MAXN];
long n, m, X[MAXN], x1, y1, x2, y2, A[100][MAXN], i;


//Functia de SORT din stl //cplusplus.com
struct Cmp {
	bool operator () (NODZ a, NODZ b) {
		if (a.x < b.x) return true;
		return false;
	}
};

void Build(long lv, long st, long dr) {
	if (st == dr) {
		A[lv][st] = P[st].y;
		return;
	}
	Build(lv + 1, st, POW);
	Build(lv + 1, POW + 1, dr);
	long i = st, j = POW + 1, k = st;
	while (i <= POW || j <= dr)	{
		if ((i <= POW && A[lv + 1][i] < A[lv + 1][j]) || j > dr) {
			A[lv][k++] = A[lv + 1][i++];
		} else {
			A[lv][k++] = A[lv + 1][j++];
		}
	}
}

long Search(long *S, long st, long dr, long y) {
	long pmax = st - 1;
	while (st <= dr) {
		if (S[POW] < y) {
			pmax = POW > pmax ? POW : pmax;
			st = POW + 1;
		} else {
			dr = POW - 1;
		}
	}
	return pmax;
}

long Query(long lv, long st, long dr) {
	if (x1 <= st && dr <= x2) {
		if (y1 > A[lv][dr] || y2 < A[lv][st]) {
			return 0;
		}
		if (y1 < A[lv][st] && A[lv][dr] < y2) {
			return (dr - st) + 1;
		}
		long ret = Search(A[lv], st, dr, y2) - Search(A[lv], st, dr, y1 - 1);
		return ret;
	}
	long ret = 0;
	if (x1 <= POW) {
		ret += Query(lv + 1, st, POW);
	}
	if (x2 >  POW) {
		ret += Query(lv + 1, POW + 1, dr);
	}
	return ret;
}

int main() {
	freopen("zoo.in", "r", stdin);
	freopen("zoo.out", "w", stdout);
	scanf("%ld", &n);
	for (i = 1; i <= n; ++i) {
		scanf("%ld%ld", &P[i].x, &P[i].y);
	}
	sort(P + 1, P + n + 1, Cmp());
	for (i = 1; i <= n; ++i) {
		X[i] = P[i].x;
	}
	Build(1, 1, n);
	scanf("%ld", &m);
	for (i = 1; i <= m; i++) {
		scanf("%ld%ld%ld%ld", &x1, &y1, &x2, &y2);
		if (x2 < X[1] || x1 > X[n]) {
			printf("0\n");
		} else {
			x1 = Search(X, 1, n, x1 - 1) + 1;
			x2 = Search(X, 1, n, x2);
			printf("%ld\n", Query(1, 1, n));
		}
	}
	return 0;
}