Cod sursa(job #3138526)

Utilizator TeodoraMaria123Serban Teodora Maria TeodoraMaria123 Data 20 iunie 2023 09:04:41
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.78 kb
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

int n, m;

class Fenwick {
private:
    vector <int> a;
    int _n;

    int lsb(int i) {
        return (i & (-i));
    }

public:
    Fenwick(int n) {
        a.resize(1 + n);
        _n = n;
    }

    void update(int pos, int value) {
        for (int i = pos; i <= _n; i += lsb(i))
            a[i] += value;
    }

    int query(int pos) {
        int ans = 0;
        for (int i = pos; i > 0; i -= lsb(i))
            ans += a[i];

        return ans;
    }
};

struct point
{
    int x, y;
};
vector <point> points;

struct event
{
    int x, y, y2, index;
    bool start;
};
vector <event> events;
struct idk
{
    int st, dr;
};
vector <idk> ans;
vector <int> ox, oy;

void reduce(vector <int> & v)
{
    vector <int> ans;
    for(int i = 0; i < v.size(); i ++)
    {
        ans.pb(v[i]);
        while(i < v.size() - 1  &&  v[i] == v[i + 1])
            i ++;
    }
    v = ans;
}

int main()
{
    ios_base :: sync_with_stdio(0);
    cin.tie(0);

    freopen("zoo.in", "r", stdin);
    freopen("zoo.out", "w", stdout);

    cin >> n;
    points.resize(n + 1);

    for(int i = 1; i <= n; i ++)
    {
        int x, y;
        cin >> x >> y;
        points[i].x = x;
        points[i].y = y;
        ox.pb(x);
        oy.pb(y);
    }

    cin >> m;
    ans.resize(m + 1);

    events.pb({0, 0, 0});
    for(int i = 1; i <= m; i ++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        ox.pb(x1 - 1);
        ox.pb(x2);
        oy.pb(y1);
        oy.pb(y2);
        events.pb({x1 - 1, y1, y2, i, 1});
        events.pb({x2, y1, y2, i, 0});
    }

    sort(ox.begin(), ox.end());
    sort(oy.begin(), oy.end());

    reduce(ox);
    reduce(oy);
//
//    for(int x : ox)
//        cout << x << " ";
//    cout << "\n";
//
//    for(int y : oy)
//        cout << y << " ";
//    cout << "\n";

    for(int i = 1; i <= n; i ++)
    {
        int x = lower_bound(ox.begin(), ox.end(), points[i].x) - ox.begin() + 1;
        int y = lower_bound(oy.begin(), oy.end(), points[i].y) - oy.begin() + 1;
        points[i].x = x;
        points[i].y = y;
//        cout << x << " " << y << "\n";
    }

    for(int i = 1; i <= 2 * m; i ++)
    {
        int x = lower_bound(ox.begin(), ox.end(), events[i].x) - ox.begin() + 1;
        int y = lower_bound(oy.begin(), oy.end(), events[i].y) - oy.begin() + 1;
        int y2 = lower_bound(oy.begin(), oy.end(), events[i].y2) - oy.begin() + 1;
        events[i].x = x;
        events[i].y = y;
        events[i].y2 = y2;
    }

    sort(events.begin() + 1, events.end(), [] (const event &a, const event &b)
    {
        if(a.x == b.x)
            return a.y < b.y;
        return a.x < b.x;
    });

    sort(points.begin() + 1, points.end(), [] (const point &a, const point &b)
    {
        if(a.x == b.x)
            return a.y < b.y;
        return a.x < b.x;
    });

    Fenwick aib(2 * m + n + 5);
    int i = 1;
    for(int j = 1; j <= 2 * m; j ++)
    {
//        cout << events[j].x << "\n";
        while(i <= n  &&  points[i].x <= events[j].x)
        {
//            cout << "aa" <<points[i].y << " " ;
            aib.update(points[i].y, 1);
            i ++;
        }
        if(events[j].start == 1)
        {
            ans[events[j].index].st = aib.query(events[j].y2) - aib.query(events[j].y - 1);
//            cout << aib.query(events[j].y2) << " " << aib.query(events[j].y - 1) << " " << events[j].index << "\n";
        }
        else
            ans[events[j].index].dr = aib.query(events[j].y2) - aib.query(events[j].y - 1);
    }

    for(int i = 1; i <= m; i ++)
        cout << ans[i].dr - ans[i].st << "\n";
    return 0;
}