Cod sursa(job #1800868)

Utilizator ArkinyStoica Alex Arkiny Data 8 noiembrie 2016 11:16:24
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.19 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;
}

struct cascading_elem
{
	int val;
	int left_pos, right_pos;

	cascading_elem(int val, int left_pos, int right_pos)
	{
		this->val = val;
		this->left_pos = left_pos;
		this->right_pos = right_pos;
	}
};

bool Comparator3(const cascading_elem &p, int val)
{
	return p.val < val;
}

bool Comparator4(int val, const cascading_elem &p)
{
	return val<p.val;
}

POINT2D p[16010];

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

void buildAINT(int X, int Y, int lv)
{
	if (X == Y)
	{
		AINT[lv].push_back(cascading_elem(p[X].y, 0, 0));
		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].val < AINT[lv * 2 + 1][j].val)
		{
			AINT[lv].push_back(cascading_elem(AINT[lv * 2][i].val, i, j));
			++i;
		}
		else
		{
			AINT[lv].push_back(cascading_elem(AINT[lv * 2 + 1][j].val, i, j));
			++j;
		}
	}

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

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

}

int query(int a, int b, int X, int Y, pair<int, int> inter, int lv)
{
	if (inter.second < inter.first)
		return 0;
	if (a <= X && Y <= b)
	{
		return inter.second - inter.first + 1;

	}

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

	if (a <= mid)
	{

		int l = AINT[lv][inter.second].left_pos;

		if (l >= AINT[lv*2].size() || AINT[2 * lv][l].val > AINT[lv][inter.second].val)
			--l;


		e1 = query(a, b, X, mid, make_pair(AINT[lv][inter.first].left_pos, l), lv * 2);

	}
	if (b>mid)
	{

		int r = AINT[lv][inter.second].right_pos;

		if (r >= AINT[lv*2+1].size() || AINT[2 * lv + 1][r].val > AINT[lv][inter.second].val)
			--r;
		
		e2 = query(a, b, mid + 1, Y, make_pair(AINT[lv][inter.first].right_pos, r), 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)
		{
			int p4 = upper_bound(AINT[1].begin(), AINT[1].end(), y2, Comparator4) - AINT[1].begin();
			int p3 = lower_bound(AINT[1].begin(), AINT[1].end(), y1, Comparator3) - AINT[1].begin();

			--p4;
			
			if (p3 <= p4)
				out << query(p1, p2, 1, N, make_pair(p3, p4), 1) << "\n";
			else
				out << "0\n";
		}
		else
			out << "0\n";
	}


	return 0;
}