Cod sursa(job #527346)

Utilizator funkydvdIancu David Traian funkydvd Data 31 ianuarie 2011 12:02:20
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int lgNMAX = 20;
const int NMAX = 20005;
pair<int, int> coord[NMAX];
vector<int> Arb[2 * NMAX];
vector< pair<int, int> > V[NMAX];
int N, M,v, w,x1, x2, y1, y2, S;
void update(int nod, int begin, int end)
{
	Arb[nod].push_back(w);
	if(begin == end) return;
	int mij = (begin + end) / 2;
	if(v <= V[mij][0].first) update(2 * nod, begin, mij);
	else update(2 * nod + 1, mij + 1, end);
}
int caut_bin(int nod, int y)
{
	int rez = 0, p = 1<<lgNMAX;
	while(p > Arb[nod].size()) p >>= 1;
	for (; p; p>>=1)
		if(p + rez < Arb[nod].size() && Arb[nod][rez + p] < y) rez += p;
	
	if(rez > 0)	rez++;
	if(rez == 0 && Arb[nod][rez] < y)	rez++;
	return rez;
}
void query(int nod, int begin, int end)
{
	if(x1 <= V[begin][0].first && V[end][0].first <= x2)
	{
		S += caut_bin(nod, y2 + 1) - caut_bin(nod, y1);
		return;
	}
	if(begin == end) return;
	int mij = (begin + end) / 2;
	if(x1 <= V[mij][0].first)  query(2 * nod, begin, mij);
	if(V[mij + 1][0].first <= x2)  query(2 * nod + 1, mij + 1, end);
}
void normalizare()
{
	sort(coord + 1, coord + N + 1);
	int NR = 0;
	for(int i = 1 ; i <= N ; i++)
		if(i > 1 && coord[i].first == coord[i - 1].first)
			V[NR].push_back(make_pair(coord[i].first, coord[i].second));
		else
			V[++NR].push_back(make_pair(coord[i].first, coord[i].second));
	
	N = NR;		
	for(int i = 1 ; i <= N ; i++)
		for(vector< pair<int, int> > :: iterator it = V[i].begin() ; it != V[i].end() ; it++)
		{
			v = it->first;
			w = it->second;
			update(1, 1, N);
		}
}
int main()
{
	freopen("zoo.in", "r", stdin);
	freopen("zoo.out", "w", stdout);
	scanf("%d", &N);
	for(int i = 1 ; i <= N ; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		coord[i].first = x;
		coord[i].second = y;
	}
	normalizare();
	for(int i = 1 ; i < 2 * N ; i++) sort(Arb[i].begin(), Arb[i].end());
	scanf ("%d", &M);
	for(int i = 1 ; i <= M ; i++)
	{
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		S = 0;
		query(1, 1, N);
		printf("%d\n", S);
	}
	return 0;
}