Cod sursa(job #170304)

Utilizator anoukAnca Dumitrache anouk Data 2 aprilie 2008 16:57:48
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <cstdio>
#include <algorithm>
#include <iostream>
#define DIM 32002
#define pivot ((st + dr) >> 1)
using namespace std;

struct Punct {
	int x, y;
};
Punct P[DIM];
int N, M, X[DIM], x1, y1, x2, y2, A[15][DIM];
struct Cmp {
	bool operator () (Punct a, Punct b)
	{
		if (a.x < b.x) return true;
		return false;
	}
};

void Build(int lv, int st, int dr)
{
	if (st == dr)
	{
		A[lv][st] = P[st].y;
		return;
	}
	Build(lv + 1, st, pivot);
	Build(lv + 1, pivot + 1, dr);
	int i = st, j = pivot + 1, k = st;
	while (i <= pivot || j <= dr)
	{
		if ((i <= pivot && 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++];
	}
}

int Search(int S[], int st, int dr, int y)
{
	int pmax = st - 1;
	while (st <= dr)
	{
		//cout << pivot << " " << st << " " << dr << " " << pmax << " " << S[pivot] << " " << y; cin.get();
		if (S[pivot] <= y)
		{
			pmax = pivot > pmax ? pivot : pmax;
			st = pivot + 1;
		}
		else
			dr = pivot - 1;
	}
	return pmax;
}

int Query(int lv, int st, int 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;
		/*cout << "search:"; cin.get();
		for (int i = st; i <= dr; i++)
			cout << A[lv][i] << " ";
		cin.get();*/
		int ret = Search(A[lv], st, dr, y2) - Search(A[lv], st, dr, y1 - 1);
		//cout << st << " " << dr << " " << ret << " " << Search(A[lv], st, dr, y2) << " " << Search(A[lv], st, dr, y1 - 1); cin.get();
		return ret;
	}
	int ret = 0;
	if (x1 <= pivot) ret += Query(lv + 1, st, pivot);
	if (x2 >  pivot) ret += Query(lv + 1, pivot + 1, dr);
	//cout << st << " " << dr << " " << ret; cin.get();
	return ret;
}

int main()
{
	FILE *fin = fopen("zoo.in", "r");
	FILE *fout = fopen("zoo.out", "w");

	fscanf(fin, "%d", &N);
	for (int i = 1; i <= N; i++)
		fscanf(fin, "%d%d", &P[i].x, &P[i].y);
	sort(P + 1, P + N + 1, Cmp());
	for (int i = 1; i <= N; i++)
		X[i] = P[i].x;
	Build(1, 1, N);
	fscanf(fin, "%d", &M);
	for (int i = 1; i <= M; i++)
	{
		fscanf(fin, "%d%d%d%d", &x1, &y1, &x2, &y2);
		//cout << i << " " << x1 << " " << y1 << " " << x2 << " " << y2; cin.get();
		if (x2 < X[1] || x1 > X[N]) fprintf(fout, "0\n");
		else
		{
			x1 = Search(X, 1, N, x1 - 1) + 1;
			x2 = Search(X, 1, N, x2);
			//cout << x1 << " " << x2; cin.get();
			int sol = Query(1, 1, N);
			//cout << sol; cin.get();
			fprintf(fout, "%d\n", sol);
		}
	}

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