Cod sursa(job #1240976)

Utilizator assa98Andrei Stanciu assa98 Data 12 octombrie 2014 14:02:15
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <fstream>
#include <algorithm>
#include <vector>

#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;
const int MAX_M = 100100;
const int INF = 2000000000;

struct NOD {
    vector<int> v;
};

vector<int> x;

vector<pe> A;

NOD aint[3 * MAX_N];

void merge_nod(NOD &a, NOD &b, NOD &c) {
    a.v.clear();
    a.v.reserve(b.v.size() + c.v.size() + 10);

    int poz1 = 0;
    int poz2 = 0;
    vector<int> &v1 = b.v;
    vector<int> &v2 = c.v;
    while(poz1 < (int)v1.size() && poz2 < (int)v2.size()) {
        if(v1[poz1] < v2[poz2]) {
            a.v.push_back(v1[poz1]);
            poz1++;
        }
        else {
            a.v.push_back(v2[poz2]);
            poz2++;
        }
    }
    for(; poz1 < (int)v1.size(); poz1++) {
        a.v.push_back(v1[poz1]);
    }
    for(; poz2 < (int)v2.size(); poz2++) {
        a.v.push_back(v2[poz2]);
    }
}

int query(int nod, int st, int dr, int a, int b, int y) {
    if(st >= a && dr <= b) {
        return upper_bound(aint[nod].v.begin(), aint[nod].v.end(), y) - aint[nod].v.begin();
    }

    int mij = (st + dr) / 2;
    int ans = 0;

    if(a <= mij) {
        ans += query(nod * 2, st, mij, a, b, y);
    }
    if(b > mij) {
        ans += query(nod * 2 + 1, mij + 1, dr, a, b, y);
    }

    return ans;
}

void build(int nod, int st, int dr) {
    if(st == dr) {
        sort(aint[nod].v.begin(), aint[nod].v.end());
        return;
    }

    int mij = (st + dr) / 2;
    build(nod * 2, st, mij);
    build(nod * 2 + 1, mij + 1, dr);
    merge_nod(aint[nod], aint[2 * nod], aint[2 * nod + 1]);
}

int main() {
    int n, m;
    fin >> n;
    for(int i = 1; i <= n; i++) {
        int a, b;
        fin >> a >> b;
        A.push_back(mp(a, b));
        x.push_back(a);
    }

    x.push_back(-INF - 1);
    sort(x.begin(), x.end());
    x.erase(unique(x.begin(), x.end()), x.end());

    int d;
    for(d = 1; d < (int) x.size() - 1; d *= 2);

    for(auto it : A) {
        int a = lower_bound(x.begin(), x.end(), it.fi) - x.begin();
        aint[d - 1 + a].v.push_back(it.se);
    }
    build(1, 1, d);


    fin >> m;
    for(int i = 1; i <= m; i++) {
        int x1, x2, y1, y2;
        fin >> x1 >> y1 >> x2 >> y2;
        x1 = lower_bound(x.begin(), x.end(), x1) - x.begin();
        x2 = lower_bound(x.begin(), x.end(), x2) - x.begin();
        fout << query(1, 1, d, x1, x2, y2) - query(1, 1, d, x1, x2, y1 - 1) << '\n';
    }

    return 0;
}