Cod sursa(job #1657091)

Utilizator SilviuIIon Silviu SilviuI Data 20 martie 2016 09:45:25
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.65 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define nmax 16010

using namespace std;

struct point { int x,y; };

struct snod {
    vector < point > x;
    vector < point > y;
};

int n,x1,y1,x2,y2,sol,m;
point t[nmax];
snod arb[3*nmax];

void build(int nod,int st,int dr)
{
    if (st==dr) {
        arb[nod].x.resize(1);
        arb[nod].y.resize(1);
        arb[nod].x[0]=t[st];
        arb[nod].y[0]=t[st];
        return;
    } else
    {
        int m=(st+dr)/2;
        build(nod*2,st,m);
        build(nod*2+1,m+1,dr);
        arb[nod].x.resize(dr-st+1);
        arb[nod].y.resize(dr-st+1);

        int i=0,j=0,nr=-1;

        while (i<m-st+1 && j<dr-m) {

            if (arb[nod*2].x[i].x<arb[nod*2+1].x[j].x) nr++,arb[nod].x[nr]=arb[nod*2].x[i],i++; else
                nr++,arb[nod].x[nr]=arb[nod*2+1].x[j],j++;

        }

        while (i<m-st+1) { nr++; arb[nod].x[nr]=arb[nod*2].x[i]; i++; }
        while (j<dr-m) { nr++; arb[nod].x[nr]=arb[nod*2+1].x[j]; j++; }

        i=0,j=0,nr=-1;

        while (i<m-st+1 && j<dr-m) {

            if (arb[nod*2].y[i].y<arb[nod*2+1].y[j].y) nr++,arb[nod].y[nr]=arb[nod*2].y[i],i++; else
                nr++,arb[nod].y[nr]=arb[nod*2+1].y[j],j++;

        }

        while (i<m-st+1) { nr++; arb[nod].y[nr]=arb[nod*2].y[i]; i++; }
        while (j<dr-m) { nr++; arb[nod].y[nr]=arb[nod*2+1].y[j]; j++; }

    }
}

int binary_searchx1(int st,int dr,int val,vector <point> &x)
{
    int sol=-1;
    while (st<=dr) {
        int m=(st+dr)/2;

        if (x[m-1].x>=val) {
            sol=m; dr=m-1;
        } else st=m+1;

    }

    return sol;
}

int binary_searchx2(int st,int dr,int val,vector <point> &x)
{
    int sol=-1;
    while (st<=dr) {
        int m=(st+dr)/2;

        if (x[m-1].x<=val) {
            sol=m; st=m+1;
        } else dr=m-1;

    }

    return sol;
}

int binary_searchy1(int st,int dr,int val,vector <point> &x)
{
    int sol=-1;
    while (st<=dr) {
        int m=(st+dr)/2;

        if (x[m-1].y>=val) {
            sol=m; dr=m-1;
        } else st=m+1;

    }

    return sol;
}

int binary_searchy2(int st,int dr,int val,vector <point> &x)
{
    int sol=-1;
    while (st<=dr) {
        int m=(st+dr)/2;

        if (x[m-1].y<=val) {
            sol=m; st=m+1;
        } else dr=m-1;

    }

    return sol;
}

void query(int nod,int st,int dr,int x1,int x2,int y1,int y2)
{
    int m=(st+dr)/2;
    int lx=binary_searchx1(1,arb[nod].x.size(),x1,arb[nod].x);
    int rx=binary_searchx2(1,arb[nod].x.size(),x2,arb[nod].x);

    if (rx-lx+1==dr-st+1) {
        int ly=binary_searchy1(1,arb[nod].y.size(),y1,arb[nod].y);
        int ry=binary_searchy2(1,arb[nod].y.size(),y2,arb[nod].y);
        if (ly!=-1 && ry!=-1) sol=sol+(rx-lx+1);
        return;
    } else
    {
        int lx=binary_searchx1(1,arb[nod*2].x.size(),x1,arb[nod*2].x);
        int rx=binary_searchx2(1,arb[nod*2].x.size(),x2,arb[nod*2].x);

        if (lx<=rx && lx!=-1) query(nod*2,st,m,x1,x2,y1,y2);

        lx=binary_searchx1(1,arb[nod*2+1].x.size(),x1,arb[nod*2+1].x);
        rx=binary_searchx2(1,arb[nod*2+1].x.size(),x2,arb[nod*2+1].x);

        if (lx<=rx && lx!=-1) query(nod*2+1,m+1,dr,x1,x2,y1,y2);
    }

}

int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);

    scanf("%d",&n);

    for (int i=1;i<=n;i++) scanf("%d %d",&t[i].x,&t[i].y);

    build(1,1,n);

    scanf("%d",&m);

    for (int i=1;i<=m;i++) {
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2); sol=0;

        query(1,1,n,x1,x2,y1,y2);

        printf("%d\n",sol);

    }

    return 0;
}