Cod sursa(job #965830)

Utilizator dragangabrielDragan Andrei Gabriel dragangabriel Data 24 iunie 2013 19:54:24
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
using namespace std;
pair<int,int> V[16001];
vector<int>A[16*16001],X;
int rez,m,n,i,j,k,st,dr,L,R,left,right,a,b,x,y;

void update(int nod,int st,int dr)
{
	if (st==dr) 
		{
			A[nod].push_back(V[st].second);
			return;
	}
	int mij=(st+dr)>>1;
	update(2*nod,st,mij);
	update(2*nod+1,mij+1,dr);
	A[nod].resize(A[2*nod].size()+A[2*nod+1].size());
	merge(A[2*nod].begin(),A[2*nod].end(),A[2*nod+1].begin(),A[2*nod+1].end(),A[nod].begin());
}

void querry(int nod,int st,int dr)
{
	if (left<=st && dr<=right)
	{
		L=lower_bound(A[nod].begin(),A[nod].end(),y)-A[nod].begin();
		R=upper_bound(A[nod].begin(),A[nod].end(),b)-A[nod].begin();
		rez=rez-L+R;
		return;
	}
	if (st==dr) return;
	int mij=(st+dr)>>1;
	if (left<=mij) querry(2*nod,st,mij);
	if (mij<right) querry(2*nod+1,mij+1,dr);
}

int main()
{
	freopen("zoo.in","r",stdin);
	freopen("zoo.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++)
			scanf("%d %d",&V[i].first,&V[i].second),X.push_back(V[i].first);
	sort(X.begin(),X.end());
	sort(V+1,V+n+1);
	scanf("%d",&m);
	update(1,1,n);
	for (i=1;i<=m;i++)
	{
		scanf("%d %d %d %d",&x,&y,&a,&b);
		rez=0;
		left=lower_bound(X.begin(),X.end(),x)-X.begin()+1;
		right=upper_bound(X.begin(),X.end(),a)-X.begin();
		querry(1,1,n);
		printf("%d\n",rez);
	}
	return 0;
}