Cod sursa(job #507721)

Utilizator APOCALYPTODragos APOCALYPTO Data 6 decembrie 2010 17:38:05
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 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,M,x1,x2,y1,y2;;
int *H[3*nmax],len[3*nmax];
ofstream fout("zoo.out");

struct cmp{
  bool operator()(const nod &i,const nod &j)const
  {
      return i.x<j.x;
  }
};

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; ) H[n][len[n]++]=H[L][i++];
    for(; j<NR; ) H[n][len[n]++]=H[R][j++];

}

inline int bsearch(int a[], int n, int l, int r)
{
    int i,cnt;
    int p=0, q=0;

    for(i=0,cnt=(1<<15);cnt; cnt/=2)
    {
        if(i+cnt<=n)
          if(a[i+cnt-1]<=r)
           i+=cnt;
    }
    q=i;

    for(i=n+1,cnt=(1<<15);cnt;cnt/=2)
    {
        if(i-cnt>=1)
          if(a[i-cnt-1]>=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;
    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);
    int n=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;
}