Cod sursa(job #998639)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 17 septembrie 2013 19:48:52
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb

#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>

typedef std::pair<int,int> Point;

const int MAX_N(16005);

int n, m;
std::vector<int> It [MAX_N << 2];
std::vector<Point> v;

inline void Read (void)
{
	std::scanf("%d",&n);
	for (int i(1), x, y ; i <= n ; ++i)
	{
		std::scanf("%d %d",&x,&y);
		v.push_back(std::make_pair(x,y));
	}
	std::scanf("%d",&m);
}

inline int Left_son (const int INDEX)
{
	return INDEX << 1;
}

inline int Right_son (const int INDEX)
{
	return (INDEX << 1) + 1;
}

void Build (int index, int left, int right)
{
	if (left == right)
	{
		It[index].push_back(v[left].second);
		return;
	}
	int mid((left + right) >> 1);
	Build(Left_son(index),left,mid);
	Build(Right_son(index),mid + 1,right);
	It[index].resize(It[Left_son(index)].size() + It[Right_son(index)].size());
	std::merge(It[Left_son(index)].begin(),It[Left_son(index)].end(),It[Right_son(index)].begin(),It[Right_son(index)].end(),It[index].begin());
}

inline void Build (void)
{
	std::sort(v.begin(),v.end());
	Build(1,0,n - 1);
}

inline int Query (int index, int left, int right, int q_left, int q_right, int q_down, int q_up)
{
	if (left == right)
		return 0;
	if (q_left <= v[left].first && v[right].first <= q_right)
		return std::upper_bound(It[index].begin(),It[index].end(),q_up) - std::lower_bound(It[index].begin(),It[index].end(),q_down);
	int mid((left + right) >> 1);
	if (q_right < v[mid + 1].first)
		return Query(Left_son(index),left,mid,q_left,q_right,q_down,q_up);
	if (q_left > v[mid].first)
		return Query(Right_son(index),mid + 1,right,q_left,q_right,q_down,q_up);
	return Query(Left_son(index),left,mid,q_left,q_right,q_down,q_up) + Query(Right_son(index),mid + 1,right,q_left,q_right,q_down,q_up);
}

int main (void)
{
	std::freopen("zoo.in","r",stdin);
	std::freopen("zoo.out","w",stdout);
	Read();
	Build();
	Point a, b;
	while (m)
	{
		std::scanf("%d %d %d %d",&a.first,&a.second,&b.first,&b.second);
		std::printf("%d\n",Query(1,0,n - 1,a.first,b.first,a.second,b.second));
		--m;
	}
	std::fclose(stdin);
	std::fclose(stdout);
	return 0;
}