Cod sursa(job #615751)

Utilizator ChallengeMurtaza Alexandru Challenge Data 10 octombrie 2011 18:50:20
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const char InFile[]="zoo.in";
const char OutFile[]="zoo.out";
const int MaxN=16111;
const int AINT_SIZE=MaxN<<2;
const int BUFFER_SIZE=5*1024*1024;

ifstream fin(InFile);
ofstream fout(OutFile);

struct point
{
	point(int x=0, int y=0):x(x),y(y){}
	int x,y;
};

struct cmp_point_x
{
	inline bool operator() (const point &a, const point &b)
	{
		return a.x<b.x;
	}
};

struct aint_node
{
	vector<int> y;
};

unsigned int ind,ind1,ind2;
int N,M,sol,xmin,ymin,xmax,ymax,pst,pdr;
aint_node aint[AINT_SIZE];
point p[MaxN];
char buffer[BUFFER_SIZE];
char *ptr=(buffer+1);

inline int number()
{
	int sol=0;
	while(!('0'<=*ptr && *ptr<='9'))
	{
		++ptr;
	}

	int sign=1;
	if(*(ptr-1)=='-')
	{
		sign=-1;
	}
	while('0'<=*ptr && *ptr<='9')
	{
		sol*=10;
		sol+=*ptr-'0';
		++ptr;
	}
	return sign*sol;
}

inline void cauta(const int &nod)
{
	int p=0,u=aint[nod].y.size()-1;
	while(p<=u)
	{
		int m=p+((u-p)>>1);
		if(aint[nod].y[m]>=ymin)
		{
			u=m-1;
		}
		else
		{
			p=m+1;
		}
	}
	int st=p;
	p=0,u=aint[nod].y.size()-1;
	while(p<=u)
	{
		int m=p+((u-p)>>1);
		if(aint[nod].y[m]<=ymax)
		{
			p=m+1;
		}
		else
		{
			u=m-1;
		}
	}
	int dr=u;
	sol+=dr-st+1;
}

void init(int nod, int st, int dr)
{
	if(st==dr)
	{
		aint[nod].y.push_back(p[st].y);
		return;
	}

	int l=nod<<1;
	int mid=st+((dr-st)>>1);

	init(l,st,mid);
	init(l+1,mid+1,dr);

	aint[nod].y.resize(dr-st+1);

	ind=0;
	ind1=0;
	ind2=0;
	while(ind1<aint[l].y.size() && ind2<aint[l+1].y.size())
	{
		if(aint[l].y[ind1]<aint[l+1].y[ind2])
		{
			aint[nod].y[ind]=aint[l].y[ind1];
			++ind1;
		}
		else
		{
			aint[nod].y[ind]=aint[l+1].y[ind2];
			++ind2;
		}
		++ind;
	}
	while(ind1<aint[l].y.size())
	{
		aint[nod].y[ind]=aint[l].y[ind1];
		++ind1;
		++ind;
	}
	while(ind2<aint[l+1].y.size())
	{
		aint[nod].y[ind]=aint[l+1].y[ind2];
		++ind2;
		++ind;
	}
}

void query(int nod, int st, int dr)
{
	if(pst<=st && dr<=pdr)
	{
		cauta(nod);
		return;
	}

	int mid=st+((dr-st)>>1);
	nod<<=1;
	if(pst<=mid)
	{
		query(nod,st,mid);
	}
	if(mid<pdr)
	{
		query(nod+1,mid+1,dr);
	}
}

int main()
{
	fin.rdbuf()->sgetn( ptr, BUFFER_SIZE-1 );
	fin.close();

	N=number();
	for(register int i=1;i<=N;++i)
	{
		p[i].x=number();
		p[i].y=number();
	}

	sort(p+1,p+1+N,cmp_point_x());

	init(1,1,N);
	
	M=number();
	for(register int i=1;i<=M;++i)
	{
		sol=0;
		xmin=number(); ymin=number(); xmax=number(); ymax=number();
		int p=1,u=N;
		while(p<=u)
		{
			int m=p+((u-p)>>1);
			if(::p[m].x>=xmin)
			{
				u=m-1;
			}
			else
			{
				p=m+1;
			}
		}
		pst=p;
		p=1;u=N;
		while(p<=u)
		{
			int m=p+((u-p)>>1);
			if(::p[m].x<=xmax)
			{
				p=m+1;
			}
			else
			{
				u=m-1;
			}
		}
		pdr=u;
		if(1<=pst && pst<=pdr && pdr<=N)
		{
			query(1,1,N);
		}
		fout<<sol<<"\n";
	}
	fout.close();
	return 0;
}