Cod sursa(job #3040677)

Utilizator caracioni_octavianCaracioni Octavian caracioni_octavian Data 30 martie 2023 11:32:12
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

#define NMAX 16003

using namespace std;

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

typedef pair<int, int> PII;

vector<PII> points(NMAX);
vector<int> coordx, tree[4 * NMAX], list[NMAX];
int N, M;

void build(int nod, int le, int ri) {
    if (le == ri) {
        swap(tree[nod], list[le]);
        sort(tree[nod].begin(), tree[nod].end());
        return;
    }

    int mid = (le + ri) / 2;
    int ls = 2 * nod, rs = 2 * nod + 1;
    build(ls, le ,mid);
    build(rs, mid + 1, ri);

    merge(tree[ls].begin(), tree[ls].end(), tree[rs].begin(), tree[rs].end(), back_inserter(tree[nod]));
}

int query(int nod, int le, int ri, int xl, int xr, int yl, int yr) {
    if (xl <= le && ri <= xr) {
        int res = upper_bound(tree[nod].begin(), tree[nod].end(), yr) - lower_bound(tree[nod].begin(), tree[nod].end(), yl);
        return res;
    }

    int ls = 2 * nod, rs = 2 * nod + 1;
    int mid = (le + ri) / 2;

    if (xr <= mid)
        return query(ls, le, mid, xl, xr, yl, yr);
    if (mid + 1 <= xl)
        return query(rs, mid + 1, ri, xl , xr, yl, yr);

    int left = query(ls, le, mid, xl, xr, yl, yr);
    int right = query(rs, mid + 1, ri, xl , xr, yl, yr);

    return (left + right);
}

int main() {

    fin >> N;
    for (int i = 1; i <= N; i++) {
        int x, y;
        fin >> x >> y;
        points[i] = {x, y};
        coordx.push_back(x);
    }

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

    for (int i = 1; i <= N; i++) {
        points[i].first = lower_bound(coordx.begin(), coordx.end(), points[i].first) - coordx.begin() + 1;
        list[points[i].first].push_back(points[i].second);
    }

    N = (int)coordx.size();
    build(1, 1, N);


    fin >> M;
    for (int i = 1; i <= M; i++) {
        int xl, xr, yl, yr;
        fin >> xl >> yl >> xr >> yr;

        xl = lower_bound(coordx.begin(), coordx.end(), xl) - coordx.begin() + 1;
        xr = upper_bound(coordx.begin(), coordx.end(), xr) - coordx.begin();

        if (xr < xl)
            fout << "0\n";
        else
            fout << query(1, 1, N, xl, xr, yl, yr) << '\n';
    }



    return 0;
}