Cod sursa(job #1800111)

Utilizator ArkinyStoica Alex Arkiny Data 7 noiembrie 2016 12:57:20
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include<fstream>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

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


typedef pair<int, int> POINT2D;

#define x first
#define y second

bool Comparator1 (const POINT2D &p, int val)
{
	return p.x < val;
}

bool Comparator2(int val, const POINT2D &p)
{
	return val<p.x;
}


POINT2D p[16010];

vector<int> AINT[16010 * 4 + 10];

void buildAINT(int X, int Y, int lv)
{
	if (X == Y)
	{
		AINT[lv].push_back(p[X].y);
		return;
	}

	buildAINT(X, (X + Y)/2, lv * 2);
	buildAINT((X + Y) / 2 + 1, Y, lv * 2 + 1);

	int i = 0, j = 0;

	while (i < AINT[lv * 2].size() && j < AINT[lv * 2 + 1].size())
	{
		if (AINT[lv * 2][i] < AINT[lv * 2 + 1][j])
		{
			AINT[lv].push_back(AINT[lv * 2][i]);
			++i;
		}
		else
		{
			AINT[lv].push_back(AINT[lv * 2 + 1][j]);
			++j;
		}
	}

	for (; i < AINT[lv * 2].size(); ++i)
	{
		AINT[lv].push_back(AINT[lv * 2][i]);
	}

	for (; j < AINT[lv * 2 + 1].size(); ++j)
	{
		AINT[lv].push_back(AINT[lv * 2  + 1][j]);
	}

}

int query(int a, int b, int X, int Y,pair<int,int> inter, int lv)
{
	if (a <= X && Y <= b)
	{
		auto p2 = upper_bound(AINT[lv].begin(), AINT[lv].end(), inter.second);
		auto p1 = lower_bound(AINT[lv].begin(), AINT[lv].end(), inter.first);


		return p2 - p1;
			
	}

	int mid = (X + Y) / 2, e1=0,e2=0;

	if (a <= mid)
	{
		e1 = query(a, b, X, mid,inter, lv * 2);
	}
	if(b>mid)
	{
		e2 = query(a, b, mid + 1, Y,inter, lv * 2 + 1);
	}

	return e1 + e2;
}

int main()
{

	int N, Q;

	in >> N;

	for (int i = 1; i <= N; ++i)
	{
		in >> p[i].x >> p[i].y;
	}

	sort(p + 1, p + N + 1, [&](const POINT2D &p1, const POINT2D &p2)
	{
		return p1.x < p2.x;
	});

	buildAINT(1, N, 1);

	in >> Q;

	for (int i = 1; i <= Q; ++i)
	{
		int x1, y1, x2, y2;

		in >> x1 >> y1 >> x2 >> y2;

		int p2 = upper_bound(p + 1, p + N + 1, x2, Comparator2) - p;
		int p1 = lower_bound(p + 1, p + N + 1, x1, Comparator1) - p;

		--p2;
		if(p1<=p2)
			out << query(p1, p2, 1, N, make_pair(y1, y2), 1)<<"\n";
	}


	return 0;
}