Cod sursa(job #634062)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 15 noiembrie 2011 16:46:51
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream fi ("zoo.in");
ofstream fo ("zoo.out");

const int dim = 16005, log = 16;
int N, M, x1, x2, y1, y2, C, c1, c2;
struct pct { int x, y; } P[dim];
vector <int> A[dim*log];

int cmp (pct a, pct b)
{
	return a.x < b.x;
}
int cmp2 (pct a, pct b)
{
	return a.y < b.y;
}

void cit ()
{
	fi >> N;
	for (int i = 1; i <= N; i++)
		fi >> P[i].x >> P[i].y;
	sort (P+1, P+N+1, cmp);
}

int cauta (int p, int u, int val, int tip, int n)
{
	int m, x;
	while (p <= u)
	{
		m = (p + u) >> 1;
		switch (tip)
		{
			case 1:
				x = P[m].x < val;
				break;
			case 2:
				x = P[m].x <= val;
				break;
			case 3:
				x = P[A[n][m]].y < val;
				break;
			case 4:
				x = P[A[n][m]].y <= val;
				break;			
		}
		if (x)
			p = m + 1;
		else
			u = m - 1;
	}
	if (tip & 1)
		return p;
	else
		return u;
}


void update (int s, int d, int n)
{
	if (s == d)
	{
		A[n].push_back (s);
		return;
	}
	
	int f1 = n<<1;
	int f2 = f1+1;
	int m = (s + d) >> 1;

	update (s  , m, f1);
	update (m+1, d, f2);
	
	int i = 0, j = 0;
	while (i < (int)A[f1].size() && j < (int)A[f2].size())
		if (cmp2 (P[A[f1][i]], P[A[f2][j]]))
			A[n].push_back (A[f1][i++]);
		else
			A[n].push_back (A[f2][j++]);
	while (i < (int)A[f1].size())
		A[n].push_back (A[f1][i++]);
	while (j < (int)A[f2].size())
		A[n].push_back (A[f2][j++]);
}

void query (int s, int d, int n)
{
	if (c1 <= s && d <= c2)
	{
		int l1 = cauta (0, (int)A[n].size()-1, y1, 3, n);
		int l2 = cauta (0, (int)A[n].size()-1, y2, 4, n);
		C += l2 - l1 + 1;
		return;
	}
	
	int m = (s + d) >> 1;
	int f1 = n << 1;
	int f2 = f1 + 1;
	
	if (c1 <= m)
		query (s  , m, f1);
	if (m  < c2)	
		query (m+1, d, f2);
}

void parc ()
{
	fi >> M;
	for (int i = 1; i <= M; i++)
	{
		fi >> x1 >> y1 >> x2 >> y2;
		c1 = cauta (1, N, x1, 1, 0);
		c2 = cauta (1, N, x2, 2, 0);
		C = 0;
		
		query (1, N, 1);
		fo << C << '\n';
	}	
}

int main ()
{
	cit ();
	update (1, N, 1);
	parc ();
	return 0;
}