Cod sursa(job #2925881)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 16 octombrie 2022 12:35:23
Problema Zoo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.06 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, y2, 0, i};
        points[++ind] = {x1, y1, 1, i};
        points[++ind] = {x2, y1, 2, i};
        points[++ind] = {x2, y2, 3, i};
    }
    P = ind;
}
///-------------------------------------
bool cmpX(const Point &a, const Point &b)
{
    if (a.x == b.x)
    {
        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)
    {
        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].x == points[i - 1].x) cntPct ++;
        else cntPct = 1;
        if (points[i].tip == -1)
        {
            g << points[i].x << " " << points[i].y << " animal \n";
            Update(1, P, 1, points[i].y);
            continue;
        }

        if (points[i].tip == 0)
        {
            sum = -Query(1, P, 1, points[i].y) + cntPct - dPuncte[points[i].idx];
        }

        if (points[i].tip == 1)
        {
            sum = Query(1, P, 1, points[i].y);
            dPuncte[points[i].idx] = cntPct;
        } 

        if (points[i].tip == 2)
        {
            g << points[i].y << "\n";
            sum = -Query(1, P, 1, points[i].y);
        }

        if (points[i].tip == 3)
        {
            sum = Query(1, P, 1, points[i].y);
        }

        ans[points[i].idx] += sum;
        g << points[i].x << " " << points[i].y << " gard cu suma: " << sum << "\n";
    }
}
///-------------------------------------
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;
}