Cod sursa(job #645242)

Utilizator rootsroots1 roots Data 8 decembrie 2011 21:31:58
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <cstdio>
#include <algorithm>

#define buffSize 262144

#define THeight 19
#define TWidth 16001

#define vSize 16001

using namespace std;

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

struct point
{
    int x,y;
}v[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 bool cmp(const point &a,const point &b)
{
    if(a.x!=b.x) return a.x<b.x;
    else return a.y<b.y;
}

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,int a,int b,int y1,int y2)
{
    if(a<=v[L].x&&v[R].x<=b)
    {
        if(y2<T[level][L]||T[level][R]<y1) return;
        else
        if(y1<=T[level][L]&&T[level][R]<=y2)
        {
            cnt+=R-L+1;
            return;
        }
        else
        {
            int pos1=BS(y1-1,level,L,R);
            int pos2=BS(y2,level,L,R);
            cnt+=pos2-pos1;
            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);
}

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

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

    sort(v+1,v+N+1,cmp);
    build(1,1,N);

    freopen("zoo.out","w",stdout);
    read(M);
    for(;M--;)
    {
        read(x1);
        read(y1);
        read(x2);
        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;
}