Cod sursa(job #3289504)

Utilizator Mihai_999Diaconeasa Mihai Mihai_999 Data 27 martie 2025 10:58:20
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.49 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#define nl '\n'

using namespace std;

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

const int NMAX = 16005, INF = 2e9;

int n, vX[NMAX], vY[NMAX];

struct node
{
    vector<int> points;
};
node aint[4*NMAX];

struct point
{
    int x, y;
};
point puncte[NMAX];

unordered_map<int,int> normX;
int kX, wayPointX[NMAX];

bool cmp(const point& a, const point& b)
{
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

void interclasare(int node)
{
    int m1 = aint[2*node].points.size();
    int m2 = aint[2*node+1].points.size();
    int i = 0, j = 0;
    while (i < m1 && j < m2)
    {
        if (aint[2*node].points[i] < aint[2*node+1].points[j])
        {
            aint[node].points.push_back(aint[2*node].points[i]);
            i++;
        }
        else
        {
            aint[node].points.push_back(aint[2*node+1].points[j]);
            j++;
        }
    }
    while (i < m1)
    {
        aint[node].points.push_back(aint[2*node].points[i]);
        i++;
    }
    while (j < m2)
    {
        aint[node].points.push_back(aint[2*node+1].points[j]);
        j++;
    }
    return;
}

int cb(int val)
{
    int low = 1, high = n, mid, sol = n+1;
    while (low <= high)
    {
        mid = (low+high)>>1;
        if (puncte[mid].x >= val)
        {
            sol = mid;
            high = mid-1;
        }
        else
            low = mid+1;
    }
    return sol;
}

void build(int node, int low, int high)
{
    if (low == high)
    {
        int poz = cb(low);
        while (poz <= n && puncte[poz].x == low)
        {
            aint[node].points.push_back(puncte[poz].y);
            poz++;
        }
        return;
    }
    int mid = (low+high)>>1;
    build(2*node, low, mid);
    build(2*node+1, mid+1, high);
    interclasare(node);
    return;
}

int cautaBin(int node, int y1, int y2)
{
    int low = 0, high = aint[node].points.size()-1, mid, poz1 = -1, poz2 = -1;
    while (low <= high)
    {
        mid = (low+high)>>1;
        if (aint[node].points[mid] >= y1)
        {
            poz1 = mid;
            high = mid-1;
        }
        else
            low = mid+1;
    }
    low = 0;
    high = aint[node].points.size()-1;
    while (low <= high)
    {
        mid = (low+high)>>1;
        if (aint[node].points[mid] <= y2)
        {
            poz2 = mid;
            low = mid+1;
        }
        else
            high = mid-1;
    }
    if (poz1 == -1 || poz2 == -1)
        return 0;
    return poz2-poz1+1;
}

int query(int node, int low, int high, int a, int b, int y1, int y2)
{
    if (a <= low && high <= b)
        return cautaBin(node, y1, y2);
    int mid = (low + high)>>1, t1 = 0, t2 = 0;
    if (a <= mid)
        t1 = query(2*node, low, mid, a, b, y1, y2);
    if (mid+1 <= b)
        t2 = query(2*node+1, mid+1, high, a, b, y1, y2);
    return t1+t2;
}

int normalise1(int val)
{
    int low = 1, high = kX, mid, sol = -1;
    while (low <= high)
    {
        mid = (low + high)>>1;
        if (wayPointX[mid] >= val)
        {
            sol = mid;
            high = mid-1;
        }
        else
            low = mid+1;
    }
    return sol;
}

int normalise2(int val)
{
    int low = 1, high = kX, mid, sol = -1;
    while (low <= high)
    {
        mid = (low+high)>>1;
        if (wayPointX[mid] <= val)
        {
            sol = mid;
            low = mid+1;
        }
        else
            high = mid-1;
    }
    return sol;
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        fin >> puncte[i].x >> puncte[i].y;
        vX[i] = puncte[i].x;
    }
    sort(vX+1, vX+1+n);
    vX[0] = INF+1;
    for (int i = 1; i <= n; i++)
    {
        if (vX[i] != vX[i-1])
        {
            normX[vX[i]] = ++kX;
            wayPointX[kX] = vX[i];
        }
    }
    for (int i = 1; i <= n; i++)
        puncte[i].x = normX[puncte[i].x];
    sort(puncte+1, puncte+1+n, cmp);
    build(1, 1, kX);
    int t;
    fin >> t;
    while (t--)
    {
        int x1, y1, x2, y2;
        fin >> x1 >> y1 >> x2 >> y2;
        x1 = normalise1(x1);
        x2 = normalise2(x2);
        if (x1 == -1 || x2 == -1)
        {
            fout << 0 << nl;
            continue;
        }
        fout << query(1, 1, kX, x1, x2, y1, y2) << nl;
    }
    return 0;
}