Cod sursa(job #2966281)

Utilizator AswVwsACamburu Luca AswVwsA Data 16 ianuarie 2023 23:13:24
Problema Zoo Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 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 == 1 and b.op == 2)
        return false;
    if (a.op == 2 and b.op == 1)
        return true;
    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;
    }
}
int main()
{
    ifstream cin("zoo.in");
    ofstream cout("zoo.out");
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    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";
}