Cod sursa(job #432704)

Utilizator hadesgamesTache Alexandru hadesgames Data 2 aprilie 2010 17:12:32
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define mp make_pair
FILE *in,*out;
int x1,y1,x2,y2;
pair<int,int> v[16005];
int * arb[16005];
void init(int nod ,int x,int y)
{
	arb[nod]=new int [y-x+5];
	if (x==y)
	{
		arb[nod][0]=v[x].se;
		return ;
	}
	int m=(x+y)/2;
	init(nod*2,x,m);
	init(nod*2+1,m+1,y);
	int lims=m-x+1,limd=y-(m+1)+1,i=0,j=0,poz=0;
	while (poz<y-x+1)
	{
		if ((arb[nod*2][i]<arb[nod*2+1][j]||j>=limd)&&i<lims)
		{
			arb[nod][poz]=arb[nod*2][i];
			i++;
		}
		else
		{
			arb[nod][poz]=arb[nod*2+1][j];
			j++;
		}
		poz++;
	}
}
int query(int nod,int x,int y,int a,int b)
{
	if (a>b)
		return 0;
	if (a<=x&&y<=b)
		return upper_bound(arb[nod],arb[nod]+y-x+1,y2)-lower_bound(arb[nod],arb[nod]+y-x+1,y1);
	int rez=0,m=(x+y)/2;
	if (a<=m)
		rez+=query(nod*2,x,m,a,b);
	if (b>m)
		rez+=query(nod*2+1,m+1,y,a,b);
	return rez;
}
int main()
{
	int n,m,i;
	in=fopen("zoo.in","r");
	out=fopen("zoo.out","w");
	fscanf(in,"%d",&n);
	for (i=1;i<=n;i++)
		fscanf(in,"%d%d",&v[i].fi,&v[i].se);
	sort(v+1,v+n+1);
	init(1,1,n);
	fscanf(in,"%d",&m);
	for (i=1;i<=m;i++)
	{
		fscanf(in,"%d%d%d%d",&x1,&y1,&x2,&y2);
		fprintf(out,"%d\n",query(1,1,n,lower_bound(v+1,v+n+1,mp(x1,y1))-v,upper_bound(v+1,v+n+1,mp(x2,y2))-v-1));
	}
	fclose(in);
	fclose(out);
	return 0;


}