Cod sursa(job #1450994)

Utilizator theprdvtheprdv theprdv Data 15 iunie 2015 17:43:16
Problema Zoo Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 2.06 kb
/* Time Complexity: O(M * log(N)) */
#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100000
#define LGN  18
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 w, int val){
	int step = LOG, k = 0;

	for (; step; step >>= 1){
		if (k + step > N) continue;
		else if ((!w ? P[k + step].x : T[0][k + step]) < val && k + step < N) k += step;
	}
	int kp = (!w ? P[k].x : T[0][k]), k1p = (!w ? P[k + 1].x : T[0][k + 1]);
	if (k1p <= val && kp != k1p && 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 && r < p2) sol += r - l + 1;
		else sol += p2 - p1;
		return;
	}
	if (p1 < 0) p1 = 0;
	if (x1 <= m) query(lv + 1, l, m, Ptr[lv][p1][0], Ptr[lv][p2][0]);
	if (x2 > m) query(lv + 1, m + 1, r, Ptr[lv][p1][1], 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);

	fscanf(fin, "%d", &M);
	for (; M; --M, sol = 0) {
		fscanf(fin, "%d %d %d %d", &x1, &y1, &x2, &y2);
		x1 = search(0, x1);
		x2 = search(0, x2);
		y1 = search(1, y1);
		y2 = search(1, y2);

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

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