Cod sursa(job #399178)

Utilizator Mishu91Andrei Misarca Mishu91 Data 19 februarie 2010 22:45:20
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <fstream>
#include <algorithm>

using namespace std;

#define x first
#define y second
#define common\
	int nst = (nod << 1), ndr = (nst | 1), mij = ((li + lf) >> 1)

const int MAX_N = 16005;

ifstream fin ("zoo.in");
ofstream fout ("zoo.out");

int N, M, *A[MAX_N << 2], st, dr, jos, sus;
pair <int, int> V[MAX_N];

void citire()
{
	fin >> N;

	for(int i = 1; i <= N; ++i)
		fin >> V[i].x >> V[i].y;

	sort(V+1, V+N+1);
}

void build(int nod, int li, int lf)
{
	if(li == lf)
	{
		A[nod] = new int[3];
		A[nod][A[nod][0] = 1] = V[li].y;
		return;
	}

	common;

	build(nst, li, mij);
	build(ndr, mij+1, lf);

	int Nl = A[nst][0], Nr = A[ndr][0], i = 1, j = 1;
	A[nod] = new int[Nl + Nr + 3];

	for(; i <= Nl && j <= Nr; )
		A[nod][++A[nod][0]] = (A[nst][i] < A[ndr][j])? A[nst][i++] : A[ndr][j++];
	for(; i <= Nl; ++i)
		A[nod][++A[nod][0]] = A[nst][i];
	for(; j <= Nr; ++j)
		A[nod][++A[nod][0]] = A[ndr][j];
}

int query(int nod, int li, int lf)
{
	if(st <= li && lf <= dr)
		return upper_bound(A[nod]+1, A[nod]+A[nod][0]+1, sus) - lower_bound(A[nod]+1, A[nod]+A[nod][0]+1, jos);

	common;

	int rez = 0;
	if(st <= mij) rez += query(nst, li, mij);
	if(mij < dr) rez += query(ndr, mij+1, lf);

	return rez;
}

int main()
{
	citire();
	build(1, 1, N);

	fin >> M;
	while(M--)
	{
		int x1, x2, y1, y2;
		fin >> x1 >> y1 >> x2 >> y2;

		st = lower_bound(V+1, V+N+1, make_pair(x1, y1)) - V;
		dr = upper_bound(V+1, V+N+1, make_pair(x2, y2)) - V - 1;
		jos = y1;
		sus = y2;

		if(st <= dr)
			fout << query(1, 1, N) << "\n";
		else
			fout << "0\n";
	}
}