Cod sursa(job #996111)

Utilizator raulstoinStoin Raul raulstoin Data 11 septembrie 2013 02:07:16
Problema Zoo Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<map>

#define NMAX 16005

using namespace std;

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

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

bool cmp(const int a,const int b)
{
	return a<b;
}

void update(int left,int right,int nod)
{
	if(left==right)
	{
		AINT[nod]=vals[left];
		return;
	}
	int middle=(left+right)/2;
	update(left,middle,2*nod);
	update(middle+1,right,2*nod+1);
	AINT[nod].resize(AINT[2*nod].size()+AINT[2*nod+1].size());
	merge(AINT[2*nod].begin(),AINT[2*nod].end(),AINT[2*nod+1].begin(),AINT[2*nod+1].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;
	}
	int middle=(left+right)/2;
	query(left,middle,2*nod);
	query(middle+1,right,2*nod+1);
}

int main()
{
	fin>>n;
	for(int i=1;i<=n;i++)
		fin>>v[i].first>>v[i].second;
	sort(v+1,v+n+1);
	
	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);
	fin>>m;
	while(m--)
	{
		sol=0;
		fin>>a>>b>>c>>d;
		it=M.upper_bound(a-1);
		if(it==M.end())
		{
			fout<<"0\n";
			continue;
		}
		a=it->second;
		it=M.upper_bound(c);
		--it;
		c=it->second;
		query(1,n,1);
		fout<<sol<<'\n';
	}
	
	return 0;
}