Cod sursa(job #844448)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 29 decembrie 2012 12:46:10
Problema Zoo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdlib.h>
using namespace std;

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

const int dim = 16002, OO = (1<<31)-1;
int N, M, K, X1, X2, Y1, Y2, R;
struct punct { int x, y; } P[dim];
vector <int> VN, AI[dim<<2];

int cmp (punct a, punct b)
{
	if (a.x == b.x)
		return a.y < b.y;
	return a.x < b.x;
}

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

void norm ()
{
	VN.push_back (-OO);
	for (int i = 1; i <= N; i++)
		if (P[i].x != VN.back())
			VN.push_back (P[i].x);
	VN.push_back (OO);
}

void interclasare (vector <int> &A, vector <int> &B, vector <int> &C)
{
	int i = 0, j = 0, k = -1;
	while (i < B.size() && j < C.size())
		if (B[i] < C[j])
			A.push_back (B[i++]);
		else
			A.push_back (C[j++]);
	while (i < B.size())
		A.push_back (B[i++]);
	while (j < C.size())
		A.push_back (C[j++]);
}

void build_ai (int nod, int st, int dr)
{
	if (st == dr)
	{
		AI[nod].push_back (P[K].y);
		for (K++; P[K].x == P[K-1].x; K++)
			AI[nod].push_back (P[K].y);
		return;
	}
	
	int m = (st + dr) >> 1, fiu = nod << 1;
	build_ai (fiu, st, m);
	build_ai (fiu + 1, m + 1, dr);
	
	interclasare (AI[nod], AI[fiu], AI[fiu+1]);
}

int cauta (vector <int> V, int val, char tip)
{
	int p = 0, u = V.size()-1, m;
	while (p <= u)
	{
		m = ((u - p) >> 1) + p;
		if (tip == 's')
			if (V[m] < val)
				p = m + 1;
			else
				u = m - 1;
		else//if (tip == 'd')
			if (V[m] <= val)
				p = m + 1;
			else
				u = m - 1;			
	}
	if (tip == 's')
		return p;
	else//if (tip == 'd')
		return u;
}

void query_ai (int nod, int st, int dr)
{
	if (X1 <= st && dr <= X2)
	{
		int p, u, m;
		
		p = 0, u = AI[nod].size()-1, m;
		while (p <= u)
		{
			m = ((u - p) >> 1) + p;
			if (AI[nod][m] < Y1)
				p = m + 1;
			else
				u = m - 1;
		}
		int RY1 = p;
		
		p = 0, u = AI[nod].size()-1, m;
		while (p <= u)
		{
			m = ((u - p) >> 1) + p;
			if (AI[nod][m] <= Y2)
				p = m + 1;
			else
				u = m - 1;			
		}		
		int RY2 = u;
		
		if (RY1 <= RY2)
			R += RY2 - RY1 + 1;
		return;
	}
	
	int m = (st + dr) >> 1, fiu = nod << 1;
	if (m >= X1)
		query_ai (fiu, st, m);
	if (m+1 <= X2)
		query_ai (fiu + 1, m + 1, dr);
}

void rez ()
{
	while (M--)
	{
		fi >> X1 >> Y1 >> X2 >> Y2;
		X1 = cauta (VN, X1, 's');
		X2 = cauta (VN, X2, 'd');
		R = 0;
		
		if (X1 <= X2)
			query_ai (1, 1, VN.size()-2);
		fo << R << '\n';
	}	
}

int main ()
{
	cit ();
	norm ();
	build_ai (1, 1, VN.size()-2);
	rez ();
	return 0;
}