Cod sursa(job #2752011)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 16 mai 2021 13:58:16
Problema Zoo Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.38 kb
#include <fstream>
#include <algorithm>
#include <climits>
#include <vector>

using namespace std;

const int NMAX = 16000;

pair<int, int> puncte[1 + NMAX];

vector<vector<int>> normalizare;

vector<int> coordX;

vector<int> aint[4 * NMAX];

vector<int> uneste(vector<int> a, vector<int> b)
{
    vector<int> c;

    int idx1 = 0;
    int idx2 = 0;

    while (idx1 < a.size() && idx2 < b.size())
    {
        if (a[idx1] < b[idx2])
        {
            c.emplace_back(a[idx1]);
            idx1++;
        }
        else
        {
            c.emplace_back(b[idx2]);
            idx2++;
        }
    }

    while (idx1 < a.size())
    {
        c.emplace_back(a[idx1]);
        idx1++;
    }

    while (idx2 < b.size())
    {
        c.emplace_back(b[idx2]);
        idx2++;
    }

    return c;
}

void build(int idx, int st, int dr)
{
    if (st > dr)
    {
        return;
    }

    if (st == dr)
    {
        aint[idx] = normalizare[st];

        return;
    }

    int mij = (st + dr) / 2;

    int fiuSt = 2 * idx;
    int fiuDr = 2 * idx + 1;

    build(fiuSt, st, mij);
    build(fiuDr, mij + 1, dr);

    aint[idx] = uneste(aint[fiuSt], aint[fiuDr]);
}

int query(int idx, int st, int dr, int x1, int y1, int x2, int y2)
{
    if (st > dr) return 0;

    if (x1 <= st && dr <= x2)
    {
        return upper_bound(aint[idx].begin(), aint[idx].end(), y2) - lower_bound(aint[idx].begin(), aint[idx].end(), y1);
    }

    int mij = (st + dr) / 2;

    int fiuSt = 2 * idx;
    int fiuDr = 2 * idx + 1;

    int sol = 0;

    if (x1 <= mij)
    {
        sol += query(fiuSt, st, mij, x1, y1, min(x2, mij), y2);
    }
    if (x2 > mij)
    {
        sol += query(fiuDr, mij + 1, dr, max(x1, mij + 1), y1, x2, y2);
    }

    return sol;
}

int main()
{
    ifstream in("zoo.in");
    ofstream out("zoo.out");

    int n;
    in >> n;

    for (int i = 1; i <= n; i++)
    {
        in >> puncte[i].first >> puncte[i].second;
    }

    n++;
    puncte[n].first = INT_MIN + 1;
    puncte[n].second = INT_MIN + 1;
    n++;
    puncte[n].first = INT_MIN + 1;
    puncte[n].second = INT_MAX - 1;
    n++;
    puncte[n].first = INT_MAX - 1;
    puncte[n].second = INT_MIN + 1;
    n++;
    puncte[n].first = INT_MAX - 1;
    puncte[n].second = INT_MAX - 1;

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

    int crtX = INT_MIN;

    for (int i = 1; i <= n; i++)
    {
        if (crtX < puncte[i].first)
        {
            crtX = puncte[i].first;
            normalizare.emplace_back();

            coordX.emplace_back(puncte[i].first);
        }

        normalizare.back().emplace_back(puncte[i].second);
    }

    for (int i = 0; i < normalizare.size(); i++)
    {
        normalizare[i].emplace_back(INT_MAX - 1);
        normalizare[i].emplace_back(INT_MIN + 1);

        sort(normalizare[i].begin(), normalizare[i].end());
    }

    build(1, 0, normalizare.size() - 1);

    int m;
    in >> m;

    for (int j = 1; j <= m; j++)
    {
        int x1, y1, x2, y2;

        in >> x1 >> y1 >> x2 >> y2;

        int idx1 = lower_bound(coordX.begin(), coordX.end(), x1) - coordX.begin();
        int idx2 = upper_bound(coordX.begin(), coordX.end(), x2) - coordX.begin() - 1;

        out << query(1, 0, normalizare.size() - 1, idx1, y1, idx2, y2) << '\n';
    }

    return 0;
}