Cod sursa(job #2292465)

Utilizator vladcoroian2001Vlad Coroian vladcoroian2001 Data 29 noiembrie 2018 16:42:15
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;
ifstream fi("zoo.in");
ofstream fo("zoo.out");
const int NMAX=16005;
int n,V[NMAX],q,x1,y1,x2,y2,ind1,ind2,sol;
pair <int,int> X[NMAX];
vector <int> arb[4*NMAX],v;
void update(int nod,int a,int b)
{
	if(a==b)
	{
		arb[nod].push_back(X[a].second);
		return ;
	}
	int mij=(a+b)/2;
	update(2*nod,a,mij);
	update(1+2*nod,mij+1,b);
	arb[nod].resize(arb[2*nod].size()+arb[1+2*nod].size());
	merge(arb[2*nod].begin(),arb[2*nod].end(),arb[1+2*nod].begin(),arb[1+2*nod].end(),arb[nod].begin());
}
	
void query(int nod,int st,int dr,int a,int b)
{
    if(a<=st && b>=dr)
    {
        sol+=upper_bound(arb[nod].begin(),arb[nod].end(),y2)-lower_bound(arb[nod].begin(),arb[nod].end(),y1);
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        query(2*nod,st,mij,a,b);
    if(b>=mij+1)
        query(2*nod+1,mij+1,dr,a,b);
 
}
int main()
{
	fi>>n;
	for(int i=1;i<=n;i++)
		fi>>X[i].first>>X[i].second;
	sort(X+1,X+n+1);
	for(int i=1;i<=n;i++)
		v.push_back(X[i].first);
	update(1,1,n);
	fi>>q;
	for(int i=1;i<=q;i++)
	{
		fi>>x1>>y1>>x2>>y2;
		if(x1>v[n-1] || x2<v[0])
		{
			fo<<"0\n";
			continue;
		}
		ind1=lower_bound(v.begin(),v.end(),x1)-v.begin()+1;
		ind2=upper_bound(v.begin(),v.end(),x2)-v.begin();
		sol=0;
		query(1,1,n,ind1,ind2);
		fo<<sol<<"\n";
	}
	fi.close();
	fo.close();
	return 0;
}