Cod sursa(job #1418669)

Utilizator assa98Andrei Stanciu assa98 Data 13 aprilie 2015 17:41:06
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.18 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>

#define pe pair<int, int>
#define mp make_pair
#define fi first
#define se second

using namespace std;

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

const int MAX_N = 16100;

class cmp {
public:
    inline bool operator () (const pe &a, const pe &b) const {
        return a.se < b.se;
    }
};

class arb {
private:
    int nr;
    arb *f1, *f2;
public:
    arb() {
        nr = 0;
        f1 = f2 = NULL;
    }

    void build(int st, int dr) {
        if(st == dr) {
            return;
        }

        int mij = (st + dr) / 2;

        f1 = new arb();
        f1->build(1, mij);

        f2 = new arb();
        f2->build(mij + 1, dr);
    }

    void add(arb *ant, int st, int dr, int p) {
        if(st == dr) {
            nr = ant->nr + 1;
            return;
        }

        int mij = (st + dr) / 2;
        if(p <= mij) {
            f1 = new arb();
            f1->add(ant->f1, st, mij, p);
            f2 = ant->f2;
        }
        else {
            f2 = new arb();
            f2->add(ant->f2, mij + 1, dr, p);
            f1 = ant->f1;
        }
        nr = f1->nr + f2->nr;
    }

    int query(int st, int dr, int x, int y) {
        if(st >= x && dr <= y) {
            return nr;
        }

        int ans = 0;
        int mij = (st + dr) / 2;
        if(x <= mij) {
            ans += f1->query(st, mij, x, y);
        }
        if(y > mij) {
            ans += f2->query(mij + 1, dr, x, y);
        }
        return ans;
    }
};

arb *R[MAX_N];

int poz[MAX_N];

vector<int> normx;
vector<int> normy;

vector<pe> v;

int main() {
    int n;
    fin >> n;
    for(int i = 1; i <= n; i++) {
        int x, y;
        fin >> x >> y;
        normx.push_back(x);
        normy.push_back(y);
        v.push_back(mp(x, y));
    }

    sort(normx.begin(), normx.end());
    normx.erase(unique(normx.begin(), normx.end()), normx.end());

    sort(normy.begin(), normy.end());
    normy.erase(unique(normy.begin(), normy.end()), normy.end());

    for(auto &it : v) {
        it.fi = lower_bound(normx.begin(), normx.end(), it.fi) - normx.begin() + 1;
        it.se = lower_bound(normy.begin(), normy.end(), it.se) - normy.begin() + 1;
    }

    int p = 1;
    for(p = 1; p < (int)normx.size(); p *= 2);

    R[0] = new arb();
    R[0]->build(1, p);

    sort(v.begin(), v.end(), cmp());
    for(int i = 0; i < n; i++) {
        poz[v[i].se] = i + 1;
        R[i + 1] = new arb();
        R[i + 1]->add(R[i], 1, p, v[i].fi);
    }


    int m;
    fin >> m;
    for(int i = 1; i <= m; i++) {
        int x1, x2, y1, y2;
        fin >> x1 >> y1 >> x2 >> y2;
        x1 = lower_bound(normx.begin(), normx.end(), x1) - normx.begin() + 1;
        x2 = upper_bound(normx.begin(), normx.end(), x2) - normx.begin();
        y1 = lower_bound(normy.begin(), normy.end(), y1) - normy.begin();
        y2 = upper_bound(normy.begin(), normy.end(), y2) - normy.begin();
        if(x1 <= x2) {
            int ans = R[poz[y2]]->query(1, p, x1, x2);
            if(y1) {
                ans -= R[poz[y1]]->query(1, p, x1, x2);
            }
            fout << ans << '\n';
        }
        else {
            fout << 0 << '\n';
        }
    }

    return 0;
}