Cod sursa(job #460325)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 1 iunie 2010 21:59:42
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define nmax 16010

int n, m, sol, start, finish, b[20][nmax], x1, x2, y1, y2;

struct nr
{
	int x, y;
} v[nmax];

int cmp(nr a, nr b)
{
	return a.x<b.x;
}

void build(int t, int l, int r)
{
	if (l==r) 
		b[t][l]=v[l].y; else
	{
		int m, p, p1, p2;
		m=(l+r)/2;
		build(t+1, l, m);
		build(t+1, m+1, r);
		p=l;
		p1=l;
		p2=m+1;
		for (; p1<=m || p2<=r; p++)
		{
			if (p1>m)
			{
				b[t][p]=b[t+1][p2];
				p2++;
			} else
			if (p2>r)
			{
				b[t][p]=b[t+1][p1];
				p1++;
			} else
			if (b[t+1][p1]<=b[t+1][p2])
			{
				b[t][p]=b[t+1][p1];
				p1++;
			} else
			if (b[t+1][p1]>b[t+1][p2])
			{
				b[t][p]=b[t+1][p2];
				p2++;
			}
		}
	}
}

int search1(int l, int r)
{
	int m, k=0;
	while (l<=r)
	{
		m=(l+r)/2;
		if (v[m].x<x1) l=m+1; else
		{
			k=m;
			r=m-1;
		}
	}
	return k;
}

int search2(int l, int r)
{
	int m, k=0;
	while (l<=r)
	{
		m=(l+r)/2;
		if (v[m].x>x2) r=m-1; else
		{
			k=m;
			l=m+1;
		}
	}
	return k;
}

int searchy1(int t, int l, int r)
{
	int m, k=0;
	while (l<=r)
	{
		m=(l+r)/2;
		if (b[t][m]<y1) l=m+1; else
		{
			r=m-1;
			k=m;
		}
	}
	return k;
}

int searchy2(int t, int l, int r)
{
	int m, k=0;
	while (l<=r)
	{
		m=(l+r)/2;
		if (b[t][m]>y2) r=m-1; else
		{
			k=m;
			l=m+1;
		}
	}
	return k;
}


void query(int t, int l, int r)
{
	if (start<=l && r<=finish)
	{
		int p1=searchy1(t,l,r);
		int p2=searchy2(t,l,r);
		if (p1<=p2 && p1 && p2) sol+=p2-p1+1;
	} else
	{
		int m=(l+r)/2;
		if (start<=m) query(t+1, l, m);
		if (m<finish) query(t+1, m+1, r);
	}
}


int main()
{
	freopen("zoo.in","r",stdin);
	freopen("zoo.out","w",stdout);
	scanf("%d",&n);
	int i, j;
	for (i=1; i<=n; i++) scanf("%d %d",&v[i].x,&v[i].y);
	sort(v+1, v+n+1, cmp);
	build(1,1,n);
	scanf("%d",&m);
	while (m--)
	{
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		start=search1(1,n);
		finish=search2(1,n);
		sol=0;
		if (start && finish) query(1,1,n);
		printf("%d\n",sol);
	}
}