Cod sursa(job #503680)

Utilizator ooctavTuchila Octavian ooctav Data 24 noiembrie 2010 12:38:03
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<deque>
#include<queue>
#include<set>
#include<vector>
using namespace std;

const int lgNMAX = 20;
const int NMAX = 20005;
//const int MMAX = 100005;
const int INF = 2000000005;
pair<int, int> coord[NMAX];
vector<int> Arb[2 * NMAX];
vector< pair<int, int> > V[NMAX];

int N, M;
int v, w;
int x1, x2, f1, f2, S;
int test;

void write()
{
	for(int i = 1 ; i < 2 * N ; i++)
	{
		for(int j = 0; j < Arb[i].size() ; j++)
			printf("%d ", Arb[i][j]);
		printf("\n");
	}
	printf("\n\n");
	//for(int i = 1 ; i <= N && coord[i].first != -INF ; i++)
		//printf("%d ", coord[i].first);
	//printf("\n\n");
	printf("////////////\n");
}

void update(int nod, int begin, int end)
{
	if(nod == 8)
		test++;
	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;
	while(p)
	{
		if(p + rez < Arb[nod].size() && Arb[nod][rez + p] < y)
			rez += p;
		p >>= 1;
	}
	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, f2 + 1) - caut_bin(nod, f1);
		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 citi()
{
	cin >> N;
	for(int i = 1 ; i <= N ; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		coord[i].first = x;
		coord[i].second = y;
	}
}

void transfera()
{
	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);
		}
}

void online()
{
	cin >> M;
	for(int i = 1 ; i <= M ; i++)
	{
		scanf("%d%d%d%d", &x1, &f1, &x2, &f2);
		S = 0;
		query(1, 1, N);
		printf("%d\n", S);
	}
}

int main()
{
	freopen("zoo.in", "r", stdin);
	freopen("zoo.out", "w", stdout);
	citi();
	transfera();
	for(int i = 2 ; i <= N ; i++)
	{
		int j = i;
		while( (j - 1) && coord[j].first != INF && (coord[j - 1].first == -INF || coord[j - 1].first == coord[j].first))
		{
			coord[j - 1].first = coord[j].first;
			coord[j].first = -INF;
			j--;
		}
	}
	for(int i = 1 ; i < 2 * N ; i++)
		sort(Arb[i].begin(), Arb[i].end());
	//write();
	online();
	return 0;
}