Cod sursa(job #162007)

Utilizator scvalexAlexandru Scvortov scvalex Data 19 martie 2008 11:32:14
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

struct Pair {
	int x, y;
};

typedef struct Pair vector[16001];
typedef int stiva[16001];
typedef stiva arbore[17];

int N, M;
vector v;
stiva X;
arbore A;

int x1, y1, x2, y2;

bool ls(const struct Pair &a, const struct Pair &b) {
	return a.x < b.x;
}

void buildTree(int lv, int left, int right) {
	if (left == right)
		A[lv][left] = v[left].y;
	else {
		int m = (left + right) / 2;
		buildTree(lv + 1, left, m);
		buildTree(lv + 1, m + 1, right);
		int l, r, i;
		for (l = left, r = m + 1, i = left; i <= right; ++i)
			if (((l <= m) && (A[lv+1][l] <= A[lv+1][r])) || (r > right))
				A[lv][i] = A[lv+1][l++];
			else
				A[lv][i] = A[lv+1][r++];
	}
}

int bsearch(stiva X, int start, int finish, int Key, int action) {
	int st = start,
		dr = finish;
	int index(0);
	while (st <= dr) {
		int mid = (st + dr) / 2;

		if (!action) {
			if (X[mid] < Key)
				st = mid + 1;
			else
				index = mid,
				dr = mid - 1;
		} else {
			if (X[mid] > Key)
				dr = mid - 1;
			else
				index = mid,
				st = mid + 1;
		}
	}

	return index;
}

int query(int lv, int st, int dr) {
	if ((x1 <= st) && (dr <= x2)) {
		if ((y1 > A[lv][dr]) || (y2 < A[lv][st]))
			return 0;

		int i1 = bsearch(A[lv], st, dr, y1, 0);
		int i2 = bsearch(A[lv], st, dr, y2, 1);

		return (i2 - i1 + 1);
	} else {
		int t = 0;
		int mid = (st + dr) / 2;
		if (x1 <= mid)
			t += query(lv + 1, st, mid);
		if (x2 > mid)
			t += query(lv + 1, mid + 1, dr);
		return t;
	}
}

int main(int argc, char *argv[]) {
	FILE *fi = fopen("zoo.in", "r");
	fscanf(fi, "%d", &N);
	for (int i(1); i <= N; ++i)
		fscanf(fi, "%d %d", &v[i].x, &v[i].y);
	sort(v + 1, v + N + 1, ls);
	for (int i = N; i >= 1; --i)
		X[i] = v[i].x;

	buildTree(1, 1, N);

	fscanf(fi, "%d", &M);
	int a, b, c, d;
	FILE *fo = fopen("zoo.out", "w");
	for (int i(1); i <= M; ++i) {
		fscanf(fi, "%d %d %d %d", &a, &b, &c, &d);

		if ((a > X[N]) || (c < X[1]) || (b > A[1][N]) || (d < A[1][1]))
			fprintf(fo, "0\n");
		else {
			x1 = bsearch(X, 1, N, a, 0);
			x2 = bsearch(X, 1, N, c, 1);
			y1 = b;
			y2 = d;

			int nr = query(1, 1, N);

			fprintf(fo, "%d\n", nr);
		}
	}
	fclose(fo);
	fclose(fi);

	return 0;
}