Cod sursa(job #1451465)

Utilizator theprdvtheprdv theprdv Data 17 iunie 2015 10:19:52
Problema Zoo Scor 50
Compilator c Status done
Runda Arhiva de probleme Marime 2.56 kb
/* Time Complexity: O(M * log(N)) 
   2D Ortogonal Range Search ( Willad-Lueker improvement ) */
#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <stdlib.h>
#define MAXN 16001
#define LGN  15
struct point
{
	int x, y;
} P[MAXN];
typedef struct point point;

int N, M, x1, y1, x2, y2, LOG, sol;
int X[MAXN], T[LGN][MAXN], Ptr[LGN][MAXN][2];

int cmp(const void *i, const void *j){
	return ((point *)i)->x - ((point *)j)->x;
}

void build(int lv, int l, int r){
	int i, j, k, m = (l + r) >> 1;
	if (l == r){
		T[lv][l] = P[l].y; return;
	}
	build(lv + 1, l, m);
	build(lv + 1, m + 1, r);

	for (i = l, j = m + 1, k = l; i <= m || j <= r;)
		if (j > r || (i <= m && T[lv + 1][i] < T[lv + 1][j]))
			Ptr[lv][k][0] = i, Ptr[lv][k][1] = j - 1,
			T[lv][k++] = T[lv + 1][i++];
		else 
			Ptr[lv][k][0] = i - 1, Ptr[lv][k][1] = j,
			T[lv][k++] = T[lv + 1][j++];
}

int search(int A[], int val, int eq){
	int step = LOG, k = 0;

	for (; step; step >>= 1){
		if (k + step >= N) continue;
		else if (!eq && A[k + step] < val) k += step;
		else if (eq && A[k + step] <= val) k += step;
	}
	if (!eq && A[k + 1] <= val && k + 1 < N) return ++k;
	return k;
}

void query(int lv, int l, int r, int p1, int p2){
	int m = (l + r) >> 1;

	if (x1 <= l && r <= x2){
		if (p1 > r || p2 < l) return;
		if (p1 < l && p2 > r) --sol;
		if (T[lv][p1] == T[0][y1] && p1 >= l) --p1;
		sol += (p2 - p1);
		return;
	}
	if (x1 <= m) query(lv + 1, l, m, p1 < l ? l - 1 : p1 > r ? m + 1 : Ptr[lv][p1][0],
					   p2 > r ? m + 1 : p2 < l ? l - 1 : Ptr[lv][p2][0]);
	if (x2 > m) query(lv + 1, m + 1, r, p1 < l ? m : p1 > r ? r + 1 : Ptr[lv][p1][1],
					  p2 > r ? r + 1 : p2 < l ? m : Ptr[lv][p2][1]);
}

int main(void)
{
	FILE *fin, *fout;
	int i;

	fin = fopen("zoo.in", "r");
	fout = fopen("zoo.out", "w");
	fscanf(fin, "%d", &N);

	for (i = 0; i < N; ++i)
		fscanf(fin, "%d %d", &P[i].x, &P[i].y);
	qsort(P, N, sizeof(point), cmp);
	build(0, 0, N - 1);

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

	fscanf(fin, "%d", &M);
	for (int i = 1; M; --M, sol = 0, ++i) {
		fscanf(fin, "%d %d %d %d", &x1, &y1, &x2, &y2);
		if (x2 < X[0] || x1 > X[N - 1] || y2 < T[0][0] || y1 > T[0][N - 1]){
			fprintf(fin, "0\n"); continue;
		}
		int x = x1, y = y1;
		x1 = search(X, x1, 0), x2 = search(X, x2, 1);
		y1 = search(T[0], y1, 0), y2 = search(T[0], y2, 1);

		if (T[0][y1] < y) ++y1;
		if (X[x1] < x) ++x1;

		query(0, 0, N - 1, y1, y2);
		fprintf(fout, "%d\n", sol);
	}

	fclose(fin), fclose(fout);
	return 0;
}