Cod sursa(job #645263)

Utilizator rootsroots1 roots Data 8 decembrie 2011 22:12:51
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.44 kb
#include <cstdio>
#include <cstring>

#define buffSize 262144

#define THeight 19
#define TWidth 16001

#define vSize 16001

#define nn 2000000000

using namespace std;

char buff[buffSize];
bool ok=true;
int ind=0,cnt,N;

struct point
{
    unsigned int x;
    int y;
}v[vSize],aux[vSize];

int T[THeight][TWidth];

inline void read(int &val)
{
    if(ok)
    {
        fread(buff,1,buffSize,stdin);
        ind=0;
        ok=false;
    }

    int neg=1;
    if(buff[ind]=='-')
    {
        neg=-1;
        if(++ind==buffSize)
        {
            fread(buff,1,buffSize,stdin);
            ind=0;
        }
    }

    for(val=0;'0'<=buff[ind]&&buff[ind]<='9';)
    {
        val*=10;
        val+=(buff[ind]-'0');

        if(++ind==buffSize)
        {
            fread(buff,1,buffSize,stdin);
            ind=0;
        }
    }

    val*=neg;

    for(;('0'>buff[ind]||buff[ind]>'9')&&buff[ind]!='-';)
        if(++ind==buffSize)
        {
            fread(buff,1,buffSize,stdin);
            ind=0;
        }
}

inline void build(int level,int L,int R)
{
    if(L==R)
    {
        T[level][L]=v[L].y;
        return;
    }

    int M=(L+R)>>1;
    build(level+1,L,M);
    build(level+1,M+1,R);

    int i0,i1,i2;
    for(i0=L-1,i1=L,i2=M+1;i1<=M&&i2<=R;)
        if(T[level+1][i1]<=T[level+1][i2]) T[level][++i0]=T[level+1][i1++];
        else T[level][++i0]=T[level+1][i2++];
    for(;i1<=M;++i1) T[level][++i0]=T[level+1][i1];
    for(;i2<=R;++i2) T[level][++i0]=T[level+1][i2];
}

inline int BS(int val,int level,int L,int R)
{
    int pos,add;

    if(val<T[level][L]) return L-1;

    for(add=1;add<R-L+1;add<<=1);
    for(pos=L;add;add>>=1)
        if(pos+add<=R&&T[level][pos+add]<=val) pos+=add;

    return pos;
}

inline void query(int level,int L,int R,unsigned int a,unsigned int b,int y1,int y2)
{
    if(a<=v[L].x&&v[R].x<=b)
    {
        if(T[level][L]<=y1||y2<=T[level][R])
        {
            int pos1=BS(y1-1,level,L,R);
            int pos2=BS(y2,level,L,R);
            cnt+=pos2-pos1;
            return;
        }
        else
        if(y2<T[level][L]||T[level][R]<y1) return;
        else
        {
            cnt+=R-L+1;
            return;
        }
    }

    int M=(L+R)>>1;
    if(a<=v[M].x) query(level+1,L,M,a,b,y1,y2);
    if(v[M+1].x<=b) query(level+1,M+1,R,a,b,y1,y2);
}

inline void radix(int byte,point *a,point *b)
{
    int count[0x800],index[0x800];

    memset(count,0,sizeof(count));
    index[0]=0;

    for(int i=1;i<=N;++i) ++count[(a[i].x>>byte)&0x7ff];
    for(int i=1;i<0x800;++i) index[i]=index[i-1]+count[i-1];
    for(int i=1;i<=N;++i) b[++index[(a[i].x>>byte)&0x7ff]]=a[i];
}

int main()
{
    int M,x,y1,y2;
    unsigned int x1,x2;

    freopen("zoo.in","r",stdin);
    read(N);
    for(int i=1;i<=N;++i)
    {
        read(x);
        read(v[i].y);
        v[i].x=x+nn;
    }

    radix(0,v,aux);
    radix(11,aux,v);
    radix(22,v,aux);
    for(int i=1;i<=N;++i) v[i]=aux[i];

    build(1,1,N);

    freopen("zoo.out","w",stdout);
    read(M);
    for(;M--;)
    {
        read(x);
        x1=x+nn;
        read(y1);
        read(x);
        x2=x+nn;
        read(y2);

        if(x2<v[1].x||v[N].x<x1)
        {
            printf("0\n");
            continue;
        }

        cnt=0;
        query(1,1,N,x1,x2,y1,y2);
        printf("%d\n",cnt);
    }

    return 0;
}