Cod sursa(job #558653)

Utilizator CBogdanCiobanu Bogdan CBogdan Data 17 martie 2011 13:15:45
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.89 kb
#include<cstdio>
#include<utility>
#include<algorithm>
#include<vector>
using namespace std;
#define pb push_back

int nmax,n,m,i,x1,x2,y1,y2,pos,a,b,sol,arb[4*16005+66],cautbin1X(int),cautbin2X(int),cautbin1Y(int,int),cautbin2Y(int,int);
vector<int> V[4*16005+66];
pair<int,int> P[16055];

void read(),solve(),upd(int,int,int),query(int,int,int),merge(int,int,int);

int main()
{
	read();
	solve();
	
	return 0;
}

void read()
{
	freopen("zoo.in","r",stdin);
	freopen("zoo.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&a,&b);P[i].first=a;P[i].second=b;
	}
	sort(P+1,P+1+n);
	for(i=1;i<=n;i++)
	{
		pos=i;
		upd(1,1,n);
	}
	merge(1,1,n);
}

void solve()
{
	scanf("%d",&m);
	for(;m;m--)
	{
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		x1=cautbin1X(x1);
		x2=cautbin2X(x2);
		sol=0;
		query(1,1,n);
		printf("%d\n",sol);
	}
}

void query(int nod,int st,int dr)
{
	if(x1<=st&&dr<=x2)
	{
		a=cautbin1Y(nod,y1);
		b=cautbin2Y(nod,y2);
		sol+=b-a+1;
		return ;
	}
	int mid=(st+dr)/2;
	if(x1<=mid)query(nod*2,st,mid);
	if(mid<x2) query(nod*2+1,mid+1,dr);
}

void upd(int nod,int st,int dr)
{
	if(st==dr)
	{
		if(nmax<nod)nmax=nod;
		arb[nod]=1;
		V[nod].pb(pos);
		return;
	}
	
	int mid=(st+dr)/2;
	if(pos<=mid)upd(nod*2,st,mid);
	else        upd(nod*2+1,mid+1,dr);
	arb[nod]=arb[nod*2]+arb[nod*2+1];
}

void merge(int nod,int l,int r)
{
	vector<int>::iterator it,iit;
	int m=(l+r)>>1;
	if(l==r)return;
	merge(nod*2,l,m);
	merge(nod*2+1,m+1,r);
	
	for(it=V[nod*2].begin(),iit=V[nod*2+1].begin();it!=V[nod*2].end()||iit!=V[nod*2+1].end();)
	{
		if(iit==V[nod*2+1].end()||(it!=V[nod*2].end()&& *it<*iit))
		{
			V[nod].pb(*it);
			it++;
		}
		else
		{
			V[nod].pb(*iit);
			iit++;
		}
	}
}

int cautbin1X(int x)
{
	int st=1,dr=n,s=999999999,mij;
	while(st<=dr)
	{
		mij=st+(dr-st)/2;
		if(P[mij].first>=x && mij<s)s=mij;
		if(P[mij].first>=x)
		{
			dr=mij-1;
			continue;
		}
		if(P[mij].first<x)
		{
			st=mij+1;
			continue;
		}
	}
	return s;
}

int cautbin2X(int x)
{
	int st=1,dr=n,mij,s=-1;
	while(st<=dr)
	{
		mij=st+(dr-st)/2;
		if(P[mij].first<=x&&s<mij)s=mij;
		if(P[mij].first<=x)
		{
			st=mij+1;
			continue;
		}
		if(P[mij].first>x)
		{
			dr=mij-1;
			continue;
		}
	}
	return s;
}

int cautbin1Y(int N,int x)
{
	int l=0,r=arb[N]-1,s=99999999,mij;
	while(l<=r)
	{
		mij=l+(r-l)/2;
		if(P[V[N][mij]].second>=x && mij<s)s=mij;
		if(P[V[N][mij]].second>=x)
		{
			r=mij-1;
			continue;
		}
		if(P[V[N][mij]].second<x)
		{
			l=mij+1;
			continue;
		}
	}
	return s;
}

int cautbin2Y(int N,int x)
{
	int st=0,dr=arb[N]-1,mij,s=-1;
	while(st<=dr)
	{
		mij=st+(dr-st)/2;
		if(P[V[N][mij]].second<=x&&s<mij)s=mij;
		if(P[V[N][mij]].second<=x)
		{
			st=mij+1;
			continue;
		}
		if(P[V[N][mij]].second>x)
		{
			dr=mij-1;
			continue;
		}
	}
	return s;
}