Cod sursa(job #749953)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 19 mai 2012 19:11:43
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

ifstream in("zoo.in");
ofstream out("zoo.out");

struct pct {
    int x, y;
};

const int N = 16010;

int n, m, x1, val1, x2, val2, x, y, rez;
pct v[N];
vector<int> aint[3*N];

inline bool cmp(const pct &a, const pct &b) {
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

inline int min(const int &a, const int &b) {
    return a < b ? a : b;
}

void build(const int &nod, const int &pozx, const int &pozy) {
    if(pozx == pozy) {
        aint[nod].push_back(v[pozx].y);
        return;
    }

    int mid = (pozx + pozy)>>1;

    build(2*nod, pozx, mid);
    build(2*nod + 1, mid + 1, pozy);

    aint[nod].resize(aint[2*nod].size() + aint[2*nod + 1].size());
    merge(aint[2*nod].begin(), aint[2*nod].end(), aint[2*nod + 1].begin(), aint[2*nod + 1].end(), aint[nod].begin());
}

inline int cb(const int &nod) {
    int j, pas = 1<<13, i;

    for(i = 0; pas; pas>>=1)
        if(i + pas < aint[nod].size() && aint[nod][i + pas] < val1)
            i += pas;

    if(aint[nod][i] >= val1)
        --i;

    pas = 1<<13;
    for(j = 0; pas; pas>>=1)
        if(j + pas < aint[nod].size() && aint[nod][j + pas] <= val2)
            j += pas;

    if(i>=j)
        return 0;

    return j - i;
}

void query(const int &nod, const int &pozx, const int &pozy) {

    if(pozx>=x && pozy<=y) {
        rez += cb(nod);

        return;
    }

    int mid = (pozx + pozy)>>1;

    if(mid >= x)
        query(2*nod, pozx, mid);
    if(mid < y)
        query(2*nod + 1, mid + 1, pozy);

}

int main() {
    int i, j, pas;

    in >> n;

    for(i = 1; i<=n; ++i)
        in >> v[i].x >> v[i].y;

    sort(v + 1, v + n + 1, cmp);

    build(1, 1, n);

    in >> m;

    for(i = 1; i<=m; ++i) {
        in >> x1 >> val1 >> x2 >> val2;

        pas = 1<<13;
        for(j = 0; pas; pas>>=1)
            if(j + pas <= n && v[j + pas].x < x1)
                j += pas;
        x = j + 1;

        pas = 1<<13;
        for(j = 0; pas; pas>>=1)
            if(j + pas <= n && v[j + pas].x <= x2)
                j += pas;
        y = j;

        rez = 0;

        query(1, 1, n);

        out << rez << "\n";
    }

    return 0;
}