Cod sursa(job #507734)

Utilizator APOCALYPTODragos APOCALYPTO Data 6 decembrie 2010 17:58:26
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
using namespace std;
#include<cstdio>
#include<fstream>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#define nmax 16005
#define common int m=(l+r)>>1, L=n<<1, R=L|1
struct nod{
int x,y;};

nod a[nmax];
int n,x1,x2,y1,y2;;
int *H[3*nmax],len[3*nmax];
ofstream fout("zoo.out");

struct cmp{
	bool operator()(const nod &a, const nod &b)const
	{
		if(a.x < b.x) return 1;
		return 0;
	}
};
void build(int n,int l, int r)
{
	if(l >= r)
	{
		H[n] = new int[3];
		H[n][len[n]++] = a[l].y;
		return;
	}

	common;

	build(L, l, m);
	build(R, m+1, r);

	int NL=len[L], NR=len[R],i,j;

	H[n]=new int[NL+NR+3];

	for(i=0, j=0; i < NL && j < NR; )
		if(H[L][i] <= H[R][j]) H[n][len[n]++] = H[L][i++];
		else 				  H[n][len[n]++] = H[R][j++];

	for(; i < NL; ++i) H[n][len[n]++] = H[L][i];
	for(; j < NR; ++j) H[n][len[n]++] = H[R][j];

}

inline int bsearch(int a[], int n, int l, int r)
{
	//if(n == 1)
	//	if(a[0] >= l && a[0] <= r) return 1;
	//	else return 0;

	int i, cnt;
	int p=0, q=0;

	for(i=0, cnt=(1<<15); cnt; cnt>>=1)
		if(i + cnt < n)
			if(a[i + cnt] <= r) i += cnt;

	q=i;

	for(i=n-1, cnt=(1<<15); cnt; cnt>>=1)
		if(i - cnt >= 0)
			if(a[i - cnt] >= l) i -= cnt;

	p=i;

	return q-p+1;
}



inline int query(int n, int l, int r, int ql, int qr)
{
	if(ql <= l && r <= qr)
	{
		if(y2 < H[n][0] || y1 > H[n][len[n]-1]) return 0;
		if(y1 <= H[n][0] && H[n][len[n]-1] <= y2) return (r-l+1);
		return bsearch(H[n], len[n], y1, y2);
	}

	common;

	int s=0;

	if(ql <= m) s += query(L, l, m, ql, qr);
	if(qr > m)  s += query(R, m+1, r, ql,qr);

	return s;
}

void cit()
{int i,cnt,M;
    ifstream fin("zoo.in");
    fin>>n;


    for(i=1;i<=n;i++)
    {
        fin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1,cmp());

    build(1,1,n);

    fin>>M;
    for(i=1;i<=M;i++)
    {
        fin>>x1>>y1>>x2>>y2;
        if(x2<a[1].x || x1>a[n].x) {fout<<"0\n";}
        else
        {

		for(i=1, cnt=(1<<15); cnt; cnt>>=1)
			if(i + cnt <= n)
				if(a[i + cnt].x <= x2) i += cnt;

		x2=i;

		for(i=n, cnt=(1<<15); cnt; cnt>>=1)
			if(i - cnt >= 1)
				if(a[i - cnt].x >= x1) i -= cnt;

		x1=i;
           fout<<query(1,1,n,x1,x2)<<"\n";
        }
    }
    fin.close();
}

int main()
{
     cit();
    fout.close();
    return 0;
}