Cod sursa(job #2900888)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 12 mai 2022 13:53:03
Problema Zoo Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.7 kb
#include <bits/stdc++.h>
#define NMAX 16005
#define MMAX 100005
#define POINTSMAX 218005

using namespace std;

/***********/
// INPUT / OUTPUT

ifstream f("zoo.in");
ofstream g("zoo.out");
/***********/
/// GLOBAL DECLARATIONS

int N, M, P;
int arb[4 * POINTSMAX], ans[MMAX], dPuncte[MMAX];

struct Point
{
    int x, y;
    short tip; // -1 -> animal, 0 -> stanga-sus, 1 -> stanga jos, 2 -> dreapta jos, 3 -> dreapta sus
    int idx;
} points[NMAX + MMAX];
/***********/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/***********/
///-------------------------------------
inline void ReadInput()
{
    f >> N;

    int x, y, ind = 0;
    for (int i = 1 ; i <= N ; ++ i)
    {
        f >> x >> y;
        points[++ind] = {x, y, -1, -1};
    }

    f >> M;

    int x1, y1, x2, y2;
    for (int i = 1 ; i <= M ; ++ i)
    {
        f >> x1 >> y1 >> x2 >> y2;
        points[++ind] = {x1 - 1, y2, 0, i};
        points[++ind] = {x1 - 1, y1 - 1, 1, i};
        points[++ind] = {x2, y1 - 1, 2, i};
        points[++ind] = {x2, y2, 3, i};
    }
    P = ind;
}
///-------------------------------------
bool cmpX(const Point &a, const Point &b)
{
    if (a.x == b.x)
    {
        if (a.y == b.y)
        {
            return a.tip < b.tip;
        }
        return a.y < b.y;
    }
    return a.x < b.x;
}
///-------------------------------------
inline void NormalizeX()
{
    sort(points + 1, points + P + 1, cmpX);

    int ind = 1, aux;
    for (int i = 1 ; i <= P ; ++ i)
    {
        aux = points[i].x;
        points[i].x = ind;
        if (aux < points[i + 1].x) ind ++;
    }
}
///-------------------------------------
bool cmpY(const Point &a, const Point &b)
{
    if (a.y == b.y)
    {
        if (a.x == b.x)
        {
            return a.tip < b.tip;
        }
        return a.x < b.x;
    }
    return a.y < b.y;
}
///-------------------------------------
inline void NormalizeY()
{
    sort(points + 1, points + P + 1, cmpY);

    int ind = 1, aux;
    for (int i = 1 ; i <= P ; ++ i)
    {
        aux = points[i].y;
        points[i].y = ind;
        if (aux < points[i + 1].y) ind ++;
    }
}
///-------------------------------------
void Update(int st, int dr, int arbIdx, int pos)
{
    if (st == dr)
    {
        arb[arbIdx] ++;
        return;
    }

    int mid = (st + dr) / 2;

    if (pos <= mid) Update(st, mid, 2 * arbIdx, pos);
    else Update(mid + 1, dr, 2 * arbIdx + 1, pos);
    arb[arbIdx] = arb[2 * arbIdx] + arb[2 * arbIdx + 1]; 
}
///-------------------------------------
int Query(int st, int dr, int arbIdx, int pos)
{
    if (st == dr)
    {
        return arb[arbIdx];
    }

    int mij = (st + dr) / 2;
    if (pos <= mij) return Query(st, mij, 2 * arbIdx, pos);
    return arb[2 * arbIdx] + Query(mij + 1, dr, 2 * arbIdx + 1, pos);
}
///-------------------------------------
inline void Solve()
{
    int sum, mult;
    int cntPct = 1;
    for (int i = 1 ; i <= P ; ++ i)
    {
        if (points[i].tip == -1)
        {
            Update(0, P, 1, points[i].y);
            continue;
        }

        sum = Query(0, P, 1, points[i].y);
        if (points[i].tip & 1) mult = 1; 
        else mult = -1;

        ans[points[i].idx] += mult * sum;
    }
}
///-------------------------------------
inline void Solution()
{
    NormalizeY();
    NormalizeX();
    Solve();
}
///-------------------------------------
inline void Output()
{
    int suma;
    for (int i = 1 ; i <= M ; ++ i)
    {
        g << ans[i] << "\n";
    }
}
///-------------------------------------
int main()
{
    ReadInput();
    Solution();
    Output();
    return 0;
}