Cod sursa(job #429063)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 29 martie 2010 20:01:16
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <stdio.h>
#include <algorithm>
#define IN "zoo.in"
#define OUT "zoo.out"
#define Lg 16005
#define Max(a,b) a>b?a:b
#define Min(a,b) a<b?a:b
#define x first
#define y second

using namespace std;

int *H[Lg*4];

int N,M,x1,x2,y1,y2,S,D,Sum;

pair <int, int > A[Lg];


void citire()
{
    scanf ("%d", &N);
    for (int i=1;i<=N;i++)
        scanf ("%d %d",&A[i].x, &A[i].y);
}

void build(int nod,int st,int dr)
{
    H[nod]=new int[dr-st+1];
    if (st==dr)
    {
        H[nod][0]=A[st].y;
        return ;
    }
    int mij=(st+dr)>>1;
    build(nod<<1, st, mij);
    build(nod<<1|1, mij+1,dr);

    int Ls=mij-st, i=0, Ns=nod<<1;
    int Ld=dr-mij-1, j=0, Nd=nod<<1|1;
    int num=0;

    while (i<=Ls || j<=Ld)
        if (i<=Ls && (H[Ns][i]<=H[Nd][j] || j>Ld))
            H[nod][num++]=H[Ns][i++];
        else
            H[nod][num++]=H[Nd][j++];
}

int Se(int X,int *A,int st,int dr)
{
    int N=dr;
    int mij;
    while (st<dr)
    {
        mij=(st+dr)>>1;
        if (A[mij]>=X)
            dr=mij-1;
        else
            st=mij+1;
    }
    st=Min(st,dr);
    while (A[st]<X && st<=N)
        st++;
    return st-1<=0?0:st-1;
}

int De(int X,int *A,int st,int dr)
{
    int N=dr;
    int mij;
    while (st<dr)
    {
        mij=(st+dr)>>1;
        if (A[mij]>=X)
            dr=mij-1;
        else
            st=mij+1;
    }
    st=Min(st,dr);
    while (A[st]<=X && st<=N)
        st++;
    return st-1<=0?0:st-1;
}

void calc(int nod,int st,int dr)
{
    if (S<=st && D>=dr)
    {
        Sum+=upper_bound(H[nod],H[nod]+dr-st+1,y2)-H[nod] + lower_bound(H[nod],H[nod]+dr-st+1,y1)-H[nod];
        return ;
    }
    int mij=(st+dr)>>1;
    if (S<=mij)
        calc(nod<<1,st,mij);
    if (D>mij)
        calc(nod<<1|1,mij+1,dr);
}

void afish()
{
    scanf ("%d ",&M);
    while (M--)
    {
        Sum=0;
        scanf ("%d %d %d %d",&x1,&y1,&x2,&y2);
        S=lower_bound(A+1,A+1+N,make_pair(x1,y1))-A;
        D=upper_bound(A+1,A+1+N,make_pair(x2,y2))-A-1;
        calc(1,1,N);
        printf("%d\n",Sum);
    }
}

int main ()
{
    freopen (IN, "r", stdin);
    freopen (OUT ,"w", stdout);
    citire();
    sort(A+1,A+N+1);
    build(1,1,N);
    afish();
    return 0;
}