Cod sursa(job #1821606)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 3 decembrie 2016 13:05:11
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

const int N = 65000;

int sol, i, n, xj, m, yj, xs, ys;
vector <int> H[N];
pair <int, int> v[N];

void build(int st,int dr,int po) {
    if (st == dr) {
        H[po].push_back(0);
        return;
    }
    int mij = (st + dr) >> 1;
    if (i <= mij) {
        build(st, mij, po << 1);
    } else {
        build(mij + 1, dr, (po << 1) + 1);
    }
    H[po].push_back(0);
}

void upd(int st, int dr, int po) {
    if (st == dr) {
        H[po][0] = v[i].second;
        return ;
    }
    int mij = (st + dr) >> 1;
    if (i <= mij) {
        upd(st, mij, po << 1);
    } else {
        upd(mij + 1, dr, (po << 1) + 1);
    }
    if (i == dr) {
        merge(H[po << 1].begin(), H[po << 1].end(), H[(po << 1) + 1].begin(), H[(po << 1) + 1].end(), H[po].begin());
    }
}
void query(int st, int dr, int po) {
    if (xj <= v[st].first && xs >= v[dr].first) {
        vector<int> :: iterator lo = lower_bound(H[po].begin(), H[po].end(), yj);
        vector<int> :: iterator hi = upper_bound(H[po].begin(), H[po].end(), ys);
        sol += hi - lo;
        return;
    }
    if(st==dr) {
        return;
    }
    int mij = (st + dr) >> 1;
    if (xj <= v[mij].first) {
        query(st, mij, po << 1);
    }
    if (xs >= v[mij + 1].first) {
        query(mij + 1, dr, (po << 1) + 1);
    }
}

int main() {
    fin >> n;
    for (i = 1; i <= n; ++i) {
        fin >> v[i].first >> v[i].second;
    }
    sort(v + 1, v + n + 1);
    for (i = 1; i <= n; ++i) {
        build(1, n, 1);
    }
    for (i = 1; i <= n; ++i) {
        upd(1, n, 1);
    }
    fin >> m;
    for (i = 1; i <= m; ++i) {
        fin >> xj >> yj >> xs >> ys;
        sol = 0;
        query(1, n, 1);
        fout << sol << "\n";
    }
    return 0;
}