Cod sursa(job #2966288)

Utilizator AswVwsACamburu Luca AswVwsA Data 16 ianuarie 2023 23:22:49
Problema Zoo Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.41 kb
#include <fstream>
#include <algorithm>
#include <map>
using namespace std;

const int NMAX = 16000;
const int QMAX = 100000;
map <int, int> y;

struct query
{
    int op;
    int x, y;

    int y1, y2;
    int ind;
} v[NMAX + QMAX * 2 + 1];
int ans[QMAX + 1];

bool cmp(query a, query b)
{
    if (a.x != b.x)
        return a.x < b.x;
    if (a.op + b.op == 3)
        return a.op > b.op;
    return a.op < b.op;
}

int aib[NMAX + QMAX * 2], cnt;
int query(int val)
{
    int ans = 0;
    while (val)
    {
        ans += aib[val];
        val -= val & -val;
    }
    return ans;
}

void update(int poz, int val)
{
    while (poz <= cnt)
    {
        aib[poz] += val;
        poz += poz & -poz;
    }
}

class InParser
{
private:
    FILE *fin;
    char *buff;
    int sp;

    char read_ch()
    {
        ++sp;
        if (sp == 4096)
        {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }

public:
    InParser(const char* nume)
    {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }

    InParser& operator >> (int &n)
    {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-')
        {
            n = 0;
            sgn = -1;
        }
        else
        {
            n = c - '0';
        }
        while (isdigit(c = read_ch()))
        {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }

    InParser& operator >> (long long &n)
    {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-')
        {
            n = 0;
            sgn = -1;
        }
        else
        {
            n = c - '0';
        }
        while (isdigit(c = read_ch()))
        {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};
int main()
{
    InParser cin("zoo.in");
    ofstream cout("zoo.out");
    int n, i;
    cin >> n;
    int dim = 0;
    for (i = 1; i <= n; i++)
    {
        dim++;
        cin >> v[dim].x >> v[dim].y;
        y[v[dim].y] = 0;
        v[dim].op = 1;
    }
    int q;
    cin >> q;
    for (i = 1; i <= q; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        y[y1] = 0;
        y[y2] = 0;

        dim++;
        v[dim].op = 2;
        v[dim].x = x1;
        v[dim].y1 = y1;
        v[dim].y2 = y2;
        v[dim].ind = i;

        dim++;
        v[dim].op = 3;
        v[dim].x = x2;
        v[dim].y1 = y1;
        v[dim].y2 = y2;
        v[dim].ind = i;
    }
    cnt = 0;
    for (pair <int, int> aux : y)
        y[aux.first] = ++cnt;
    sort(v + 1, v + dim + 1, cmp);
    for (i = 1; i <= dim; i++)
    {
        if (v[i].op == 1)
        {
            v[i].y = y[v[i].y];

            update(v[i].y, 1);
        }
        else
        {
            v[i].y1 = y[v[i].y1];
            v[i].y2 = y[v[i].y2];
            if (v[i].op == 2)
            {
                ans[v[i].ind] -= query(v[i].y2) - query(v[i].y1 - 1);
            }
            else
            {
                ans[v[i].ind] += query(v[i].y2) - query(v[i].y1 - 1);
            }
        }
    }
    for (i = 1; i <= q; i++)
        cout << ans[i] << "\n";
}