Cod sursa(job #3164557)

Utilizator PatruMihaiPatru Mihai PatruMihai Data 3 noiembrie 2023 17:31:38
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.93 kb
#include <bits/stdc++.h>

using namespace std;

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

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

const int NMAX = 16007;
const int MMAX = 1e5 + 7;


pair<int, int> p[NMAX];
vector<dreapta> d(MMAX);
int sol, k;
int s[MMAX * 5];

vector<int> v[5 * MMAX];

void build(int nod, int st, int dr)
{
    for (int i = st; i <= dr; i++)
    {
        v[nod].push_back(p[i].second);
    }

    sort(v[nod].begin(), v[nod].end());

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

int cautaPrimul(int x, int nod)
{
    int st = 0;
    int dr = v[nod].size() - 1;

    while (st <= dr)
    {
        int mid = (st + dr) / 2;

        if (v[nod][mid] >= x)
            dr = mid - 1;
        else
            st = mid + 1;
    }
    return st;
}

int cautaUltimul(int x, int nod)
{
    int st = 0;
    int dr = v[nod].size() - 1;

    while (st <= dr)
    {
        int mid = (st + dr) / 2;

        if (v[nod][mid] <= x)
            st = mid + 1;
        else
            dr = mid - 1;
    }
    return dr;
}

int cauta(int x)
{
    int st = 0;
    int dr = k - 1;

    while (st <= dr)
    {
        int mid = (st + dr) / 2;

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

void query(int nod, int st, int dr, int poz)
{
    if (st > dr)
        return;
    if (d[poz].x1 <= p[st].first && d[poz].x2 >= p[dr].first)
        sol += (cautaUltimul(d[poz].y2, nod) - cautaPrimul(d[poz].y1, nod) + 1);

    else
    {
        if (st == dr)
            return;

        int mid = (st + dr) / 2;

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

int main()
{
    int n, m;
    fin >> n;

    for (int i = 1; i <= n; i++)
    {
        fin >> p[i].first >> p[i].second;
        s[k++] = p[i].first;
        s[k++] = p[i].second;
    }
    fin >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> d[i].x1 >> d[i].y1 >> d[i].x2 >> d[i].y2;
        s[k++] = d[i].x1;
        s[k++] = d[i].y1;
        s[k++] = d[i].x2;
        s[k++] = d[i].y2;
    }
    sort(s, s + k);
    int last = 0;
    for (int i = 1; i < k; i++)
    {
        if (s[i] != s[last])
        {
            s[++last] = s[i];
        }
    }
    k = last + 1;
    for (int i = 1; i <= n; i++)
    {
        p[i].first = cauta(p[i].first);
        p[i].second = cauta(p[i].second);
    }
    for (int i = 1; i <= m; i++)
    {
        d[i].x1 = cauta(d[i].x1);
        d[i].y1 = cauta(d[i].y1);
        d[i].x2 = cauta(d[i].x2);
        d[i].y2 = cauta(d[i].y2);
    }

    sort(p + 1, p + n + 1);
    build(1, 1, n);
    for (int i = 1; i <= m; i++)
    {
        sol = 0;
        query(1, 1, n, i);
        fout << sol << "\n";
    }

    return 0;
}