Cod sursa(job #2750739)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 13 mai 2021 00:12:54
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.21 kb
#include <fstream>
#include <algorithm>
#include <unordered_map>
#include <vector>

using namespace std;

const int NMAX = 16000;

unordered_map<int, int> normX;
unordered_map<int, int> normY;

vector<int> coordX;
vector<int> coordY;

vector<pair<int, int>> puncte;

int mat[1 + NMAX + 2][1 + NMAX + 2];

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

    int n;
    in >> n;

    coordX.push_back(-2000000001);
    coordX.push_back(2000000001);

    coordY.push_back(-2000000001);
    coordY.push_back(2000000001);

    for (int i = 1; i <= n; i++)
    {
        int x, y;

        in >> x >> y;

        puncte.emplace_back(x, y);

        coordX.push_back(x);
        coordY.push_back(y);
    }

    sort(coordX.begin(), coordX.end());
    sort(coordY.begin(), coordY.end());

    for (int i = 0; i < coordX.size(); i++)
    {
        normX[coordX[i]] = i + 1;
    }
    for (int j = 0; j < coordY.size(); j++)
    {
        normY[coordY[j]] = j + 1;
    }

    for (int i = 0; i < puncte.size(); i++)
    {
        mat[normX[puncte[i].first]][normY[puncte[i].second]]++;
    }

    for (int i = 1; i <= n + 2; i++)
    {
        for (int j = 1; j <= n + 2; j++)
        {
            mat[i][j] = mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1] + mat[i][j];
        }
    }

    int m;
    in >> m;

    int st;
    int dr;

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

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

        st = 0;
        dr = coordX.size() - 1;

        int solX1 = coordX.size() - 1;

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

            if (coordX[mij] >= x1)
            {
                solX1 = mij;
                dr = mij - 1;
            }
            else
            {
                st = mij + 1;
            }
        }

        st = 0;
        dr = coordX.size() - 1;

        int solX2 = 0;

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

            if (coordX[mij] <= x2)
            {
                solX2 = mij;
                st = mij + 1;
            }
            else
            {
                dr = mij - 1;
            }
        }

        st = 0;
        dr = coordY.size() - 1;

        int solY1 = coordY.size() - 1;

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

            if (coordY[mij] >= y1)
            {
                solY1 = mij;
                dr = mij - 1;
            }
            else
            {
                st = mij + 1;
            }
        }

        st = 0;
        dr = coordY.size() - 1;

        int solY2 = 0;

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

            if (coordY[mij] <= y2)
            {
                solY2 = mij;
                st = mij + 1;
            }
            else
            {
                dr = mij - 1;
            }
        }

        solX1++;
        solY1++;

        solX2++;
        solY2++;

        out << mat[solX2][solY2] - mat[solX2][solY1 - 1] - mat[solX1 - 1][solY2] + mat[solX1 - 1][solY1 - 1] << '\n';
    }

    return 0;
}