Cod sursa(job #557383)

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

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

void read(),solve(),upd(int,int,int),query(int,int,int),merge(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",&a);P[i].first=a;
		scanf("%d",&b);P[i].second=b;
	}
	sort(P+1,P+1+n);
	for(i=1;i<=n;i++)
	{
		pos=i;
		upd(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)
	{
		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];
	V[nod].clear();
	merge(nod);
}

void merge(int nod)
{
	vector<int>::iterator it;
	vector<int>::iterator iit;
	for(it=V[nod*2].begin(),iit=V[nod*2+1].begin();it!=V[nod*2].end()||iit!=V[nod*2+1].end();)
	{
		if(it==V[nod*2].end() )
		{
			for(;iit!=V[nod*2+1].end();iit++)V[nod].pb(*iit);
			break;
		}
		if(iit==V[nod*2+1].end() )
		{
			for(;it!=V[nod*2].end();it++)V[nod].pb(*it);
			break;
		}
		if(P[*it].second<=P[*iit].second)
		{
			V[nod].pb(*it);
			it++;
			continue;
		}
		if(P[*iit].second<P[*it].second)
		{
			V[nod].pb(*iit);
			iit++;
			continue;
		}
	}
}

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;
}