Cod sursa(job #1720074)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 21 iunie 2016 12:39:43
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <algorithm>
#include <cstdio>
#include <vector>

const int NMAX = 16005;

struct PII {
    int x, y;

    inline PII() { }
    inline PII(int _x, int _y) {
        x = _x;
        y = _y;
    }

    bool operator <(PII arg) const {
        if(x==arg.x)
            return y<arg.y;
        return x<arg.x;
    }
};


int n, m, qx1, qx2, qy1, qy2, stb, drb;
std::vector<int> pom[NMAX * 4];
PII                v[NMAX];


void merge(std::vector<int> &c, std::vector<int> &b, std::vector<int> &a) {
    c.clear();
    int i = 0,
        j = 0;

    for(; i<a.size() && j<b.size(); ) {
        if(a[i]<b[j])
            c.push_back(a[i++]);
        else
            c.push_back(b[j++]);
    }

    for(; i<a.size(); i++)
        c.push_back(a[i]);

    for(; j<b.size(); j++)
        c.push_back(b[i]);
}

void make_pom(int nod, int st, int dr) {
    int m = (st + dr) / 2;

    if(st==dr) {
        pom[nod].push_back(v[m].y);
    }
    else {
        make_pom(2*nod,    st,  m);
        make_pom(2*nod+1, m+1, dr);

        merge(pom[nod], pom[2*nod], pom[2*nod+1]);
    }
}

int q_pom(int nod, int st, int dr) {
    int ans = 0;

    if(stb<=st && dr<=drb) {
        int a = -1,
            b = -1;

        for(int m=1<<30; m; m>>=1)
            if(a+m<pom[nod].size() && pom[nod][a+m]<qy1)
                a+=m;

        for(int m=1<<30; m; m>>=1)
            if(b+m<pom[nod].size() && pom[nod][b+m]<=qy2)
                b+=m;

        return b - a;
    }
    else {
        int m = (st + dr) / 2;

        if(m>=stb) ans+= q_pom(2*nod,    st,  m);
        if(m< drb) ans+= q_pom(2*nod+1, m+1, dr);

        return ans;
    }
}

int query(void) {
    int m, st, dr;
    st = 0,
    dr = 0;

    for(m=1<<30; m; m>>=1)
        if(st+m<=n && v[st+m].x<qx1)
            st+=m;

    for(m=1<<30; m; m>>=1)
        if(dr+m<=n && v[dr+m].x<=qx2)
            dr+=m;

    stb = st + 1;
    drb = dr;

    if(st>dr)
        return 0;

    return q_pom(1, 1, n);
}

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

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

    std::sort(v+1, v+n+1);
    make_pom(1, 1, n);

    scanf("%d",&m);
    while(m--) {
        scanf("%d%d%d%d",&qx1,&qy1,&qx2,&qy2);
        printf("%d\n",query());
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}