Cod sursa(job #826819)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 1 decembrie 2012 11:55:56
Problema Zoo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAx 16100
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
using namespace std;

vector <int> AI[4*NMAx];
struct Punct{int X,Y;}V[NMAx];
int N;

int BinarySearch(int Nod,int Val) {
	
	int i,step;
	
	for(step=1;step<=AI[Nod].size();step<<=1);
	
	for(i=0;step;step>>=1)
		if(i+step<AI[Nod].size()&&AI[Nod][i+step]<Val)
			i+=step;
	
	if(AI[Nod][i]>=Val)
		i--;
	return i;
	
}
int Query(int Nod,int Left,int Right,int A,int B,int C,int D) {
	
	int Mid=(Left+Right)>>1;
	
	if(A<=V[Left].X&&V[Right].X<=B)
		return (BinarySearch(Nod,D+1)-BinarySearch(Nod,C));
	
	if(B<V[Mid+1].X)
		return Query(2*Nod,Left,Mid,A,B,C,D);
	
	if(A>V[Mid].X)
		return Query(2*Nod+1,Mid+1,Right,A,B,C,D);
	
	return Query(2*Nod,Left,Mid,A,V[Mid].X,C,D)+Query(2*Nod+1,Mid+1,Right,V[Mid+1].X,B,C,D);
	
}
void Build(int Nod,int Left,int Right) {
	
	if(Left==Right) {
		AI[Nod].push_back(V[Left].Y);
		return;
		}
	
	int Mid=(Left+Right)>>1;
	Build(2*Nod,Left,Mid);
	Build(2*Nod+1,Mid+1,Right);
	
	AI[Nod].resize(AI[2*Nod].size()+AI[2*Nod+1].size());
	merge(AI[2*Nod].begin(),AI[2*Nod].end(),AI[2*Nod+1].begin(),AI[2*Nod+1].end(),AI[Nod].begin());
	
}
bool cmp(Punct A,Punct B) {
	
	if(A.X==B.X)
		return A.Y<B.Y;
	else
		return A.X<B.X;
	
}
void Solve(ifstream & in) {
	
	int M,A,B,C,D;
	
	ofstream out("zoo.out");
	
	sort(V+1,V+N+1,cmp);
	Build(1,1,N);
	
	in>>M;
	
	while(M--) {
		
		in>>A>>C>>B>>D;
		
		A=max(A,V[1].X);
		B=min(B,V[N].X);
		
		out<<Query(1,1,N,A,B,C,D)<<'\n';
		
		}
	
	out.close();
	
}
void Citire(ifstream & in) {
	
	in>>N;
	for(int i=1;i<=N;i++)
		in>>V[i].X>>V[i].Y;
	
}
int main() {
	
	ifstream in("zoo.in");
	Citire(in);
	Solve(in);
	in.close();
	
	return 0;
	
}