Cod sursa(job #826843)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 1 decembrie 2012 12:12:45
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 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;


///////////////////////
#define MaxBuffer 8192
char buffer[MaxBuffer];
int bufferIndex=8191;

inline void read_buffer(istream& in,int& x) {
	do {if(++bufferIndex==MaxBuffer) {
		bufferIndex=0;
		in.read(buffer,MaxBuffer);
		}
	}while( buffer[bufferIndex]<'0'||buffer[bufferIndex]>'9' );
 
	for(x=0;buffer[bufferIndex]>='0'&&buffer[bufferIndex]<= '9';) {
		x=x*10+buffer[bufferIndex]-'0';
		if(++bufferIndex==MaxBuffer) {
			bufferIndex=0;
			in.read(buffer,MaxBuffer);
			}
		}
}
////////////////////////

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(Left==Right)
		return 0;
	
	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);
	
	read_buffer(in,M);
	
	while(M--) {
		
		read_buffer(in,A);
		read_buffer(in,C);
		read_buffer(in,B);
		read_buffer(in,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) {
	
	read_buffer(in,N);
	for(int i=1;i<=N;i++) {
		read_buffer(in,V[i].X);
		read_buffer(in,V[i].Y);
		}
	
}
int main() {
	
	ifstream in("zoo.in");
	Citire(in);
	Solve(in);
	in.close();
	
	return 0;
	
}