Cod sursa(job #2966293)

Utilizator AswVwsACamburu Luca AswVwsA Data 16 ianuarie 2023 23:34:35
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.84 kb
#include <fstream>
#include <algorithm>
using namespace std;

const int NMAX = 16000;
const int QMAX = 100000;

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;
    }
}
pair <int, int> val[NMAX + 2 * QMAX + 1];

int siz;
int norm(int x)
{
    int med, st = 1, dr = siz;
    while (st <= dr)
    {
        med = ((st + dr) >> 1);
        if (val[med].first < x)
            st = med + 1;
        else if (val[med].first > x)
            dr = med - 1;
        else
            return val[med].second;
    }
}
int main()
{
    ifstream 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;
        v[dim].op = 1;
        val[++siz].first = v[dim].y;
    }
    int q;
    cin >> q;
    for (i = 1; i <= q; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        val[++siz].first = y1;
        val[++siz].first = y2;

        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 = 1;
    sort(val + 1, val + siz + 1);
    for (i = 1; i + 1 <= siz; i++)
    {
        val[i].second = cnt;
        if (val[i].first != val[i + 1].first)
        {
            cnt++;
        }
    }
    val[i].second = cnt;
    cnt++;
    /*for (i = 1; i <= siz; i++)
        cout << val[i].first << " ";
    cout << "\n";
    for (i = 1; i <= siz; i++)
        cout << val[i].second << " ";
    //return 0;*/
    sort(v + 1, v + dim + 1, cmp);
    for (i = 1; i <= dim; i++)
    {
        if (v[i].op == 1)
        {
            v[i].y = norm(v[i].y);

            update(v[i].y, 1);
        }
        else
        {
            v[i].y1 = norm(v[i].y1);
            v[i].y2 = norm(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";
}