Cod sursa(job #3163838)

Utilizator dragoncrackCandidatu Mario Luca dragoncrack Data 1 noiembrie 2023 12:34:26
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.31 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

struct drept {
    int x1;
    int x2;
    int y1;
    int y2;
};

drept q;
pair<int, int> p[16001];
vector<int> AINT[4 * 16001];
//int s[250001];
int n, m, k;

void build(int nod, int st, int dr) {
    for (int i = st; i <= dr; i++) {
        AINT[nod].push_back(p[i].second);
    }
    sort(AINT[nod].begin(), AINT[nod].end());
    if (st >= dr)
        return;
    int mid = (st + dr) / 2;
    build(2 * nod, st, mid);
    build(2 * nod + 1, mid + 1, dr);
}

int positionOfEnd(int x, int nod) {
    int position = 0;
    int st = 0;
    int dr = AINT[nod].size() - 1;
    while (st <= dr) {
        int mid = (st + dr) / 2;
        if (AINT[nod][mid] <= x) {
            position = mid;
            st = mid + 1;
        }
        else {
            position = mid - 1;
            dr = mid - 1;
        }
    }
    return position;
}

int positionOfStart(int x, int nod) {
    int position = 0;
    int st = 0;
    int dr = AINT[nod].size() - 1;
    while (st <= dr) {
        int mid = (st + dr) / 2;
        if (x <= AINT[nod][mid]) {
            position = mid;
            dr = mid - 1;
        }
        else {
            position = mid + 1;
            st = mid + 1;
        }
    }
    return position;
}

int elementsInInterval(int start, int end, int nod) {
    return positionOfEnd(end, nod) - positionOfStart(start, nod) + 1;
}

int query(int nod, int st, int dr, drept &d) {
    if (st > dr)
        return 0;
    if (d.x1 <= p[st].first && p[dr].first <= d.x2) {
        return elementsInInterval(d.y1, d.y2, nod);
    }
    else {
        if (st >= dr)
            return 0;

        int mid = (st + dr) / 2;
        int elements = 0;

        if (d.x1 <= p[mid].first)
            elements += query(2 * nod, st, mid, d);
        if (p[mid + 1].first <= d.x2)
            elements += query(2 * nod + 1, mid + 1, dr, d);

        return elements;
    }
}

/*
int normalizedValue(int x) {
    int st = 1;
    int dr = k;
    while (st <= dr) {
        int mid = (st + dr) / 2;
        if (s[mid] == x)
            return mid;

        if (x < s[mid])
            dr = mid - 1;
        else
            st = mid + 1;
    }
}
*/

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> p[i].first >> p[i].second;
       // s[++k] = p[i].first;
    }

    /*
    fin >> m;
    for (int i = 1; i <= m; i++) {
        fin >> q[i].x1 >> q[i].y1 >> q[i].x2 >> q[i].y2;
        s[++k] = q[i].x1;
        s[++k] = q[i].x2;
    }
    */

    /*
    sort(s + 1, s + k + 1);
    
    int last = 0;
    s[++last] = s[1];
    for (int i = 2; i <= k; i++) {
        if (s[i] != s[i - 1]) {
            s[++last] = s[i];
        }
    }
    k = last;

    for (int i = 1; i <= n; i++) {
        p[i].first = normalizedValue(p[i].first);
    }
    for (int i = 1; i <= m; i++) {
        q[i].x1 = normalizedValue(q[i].x1);
        q[i].x2 = normalizedValue(q[i].x2);
    }
    */

    sort(p + 1, p + n + 1);

    build(1, 1, n);
    fin >> m;
    for (int i = 1; i <= m; i++) {
        fin >> q.x1 >> q.y1 >> q.x2 >> q.y2;
        fout << query(1, 1, n, q) << "\n";
    }
}