Cod sursa(job #996121)

Utilizator raulstoinStoin Raul raulstoin Data 11 septembrie 2013 02:33:03
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<map>

#define NMAX 16005
#define middle ((left+right)>>1)
#define F1 (nod<<1)
#define F2 (F1+1)

using namespace std;

ifstream fin("zoo.in");
ofstream fout("zoo.out");

int n,m,sol,a,b,c,d,minx,maxx;
vector<int> AINT[4*NMAX],vals[NMAX];
pair<int,int> v[NMAX];
map<int,int> M;
map<int,int>::iterator it;

//
const int SZ=6500000;
char input[SZ+1],*in=input;
//

inline bool check()
{
	return (*in>='0' && *in<='9');
}

int atoi()
{
	int minus=1,nr=0;
	for(;!check() && *in!='-';in++);
	if(*in=='-')
		minus=-1,in++;
	for(;check();in++)
		nr=nr*10+(*in-'0');
	return nr*minus;
}
	
inline bool cmp(const int a,const int b)
{
	return a<b;
}

inline void update(int left,int right,int nod)
{
	if(left==right)
	{
		AINT[nod]=vals[left];
		return;
	}
	update(left,middle,F1);
	update(middle+1,right,F2);
	AINT[nod].resize(AINT[F1].size()+AINT[F2].size());
	merge(AINT[F1].begin(),AINT[F1].end(),AINT[F2].begin(),AINT[F2].end(),AINT[nod].begin(),cmp);
}

void query(int left,int right,int nod)
{
	if(left>c || right<a)
		return;
	if(a<=left && right<=c)
	{
		sol+=(int)(upper_bound(AINT[nod].begin(),AINT[nod].end(),d)-upper_bound(AINT[nod].begin(),AINT[nod].end(),b-1));
		return;
	}
	query(left,middle,F1);
	query(middle+1,right,F2);
}

int main()
{
	fin.read(input,SZ);
	n=atoi();
	for(int i=1;i<=n;i++)
		v[i].first=atoi(),v[i].second=atoi();
	sort(v+1,v+n+1);
	minx=v[1].first;
	maxx=v[n].first;
	
	for(int i=1,j=0;i<=n;i++)
		if(M.find(v[i].first)==M.end())
			M.insert(make_pair(v[i].first,++j));
	it=M.begin();
	for(int i=1,poz;i<=n;i++,it++)
	{
		poz=it->second;
		for(;v[i].first==it->first && i<=n;i++)
			vals[poz].push_back(v[i].second);
		i--;
	}
	n=M.size();
	update(1,n,1);
	m=atoi();
	while(m--)
	{
		sol=0;
		a=atoi(),b=atoi(),c=atoi(),d=atoi();
		if(a>maxx || c<minx)
		{
			fout<<"0\n";
			continue;
		}
		it=M.upper_bound(a-1);
		a=it->second;
		it=M.upper_bound(c);
		--it;
		c=it->second;
		query(1,n,1);
		fout<<sol<<'\n';
	}
	
	return 0;
}