Cod sursa(job #3193787)

Utilizator octavian202Caracioni Octavian Luca octavian202 Data 15 ianuarie 2024 18:18:34
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

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

const int NMAX = 16005;
pair<int, int> points[NMAX];
vector<int> cordx, list[NMAX];
vector<int> aint[4 * NMAX];


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

    int mid = (st + dr) / 2;
    build(2 * nod, st, mid);
    build(2 * nod + 1, mid + 1, dr);

    merge(
            aint[2 * nod].begin(),
            aint[2 * nod].end(),
            aint[2 * nod + 1].begin(),
            aint[2 * nod + 1].end(),
            back_inserter(aint[nod])
    );
}

int query(int nod, int st, int dr, int i1, int j1, int i2, int j2) {
    if (i1 <= st && dr <= i2) {
        return (upper_bound(aint[nod].begin(), aint[nod].end(), j2) - lower_bound(aint[nod].begin(), aint[nod].end(), j1));
    }

    int mid = (st + dr) / 2;
    int res = 0;
    if (i1 <= mid)
        res += query(2 * nod, st, mid, i1, j1, i2, j2);
    if (mid + 1 <= i2)
        res += query(2 * nod + 1, mid + 1, dr, i1, j1, i2, j2);

    return res;
}

int main() {

    int n;
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> points[i].first >> points[i].second;
        cordx.push_back(points[i].first);
    }

    sort(cordx.begin(), cordx.end());
    cordx.resize(unique(cordx.begin(), cordx.end()) - cordx.begin());
    for (int i = 1; i <= n; i++) {
        points[i].first = lower_bound(cordx.begin(), cordx.end(), points[i].first) - cordx.begin() + 1;
        list[points[i].first].push_back(points[i].second);
    }

    int l = cordx.size();
    build(1, 1, l);

    int q;
    fin >> q;
    while (q--) {
        int i1, j1, i2, j2;
        fin >> i1 >> j1 >> i2 >> j2;

        i1 = lower_bound(cordx.begin(), cordx.end(), i1) - cordx.begin() + 1;
        i2 = upper_bound(cordx.begin(), cordx.end(), i2) - cordx.begin();

        if (i1 > i2) {
            fout << "0\n";
        } else {
            fout << query(1, 1, l, i1, j1, i2, j2) << '\n';
        }
    }



    return 0;
}