Cod sursa(job #2831922)

Utilizator MatteoalexandruMatteo Verzotti Matteoalexandru Data 12 ianuarie 2022 14:17:59
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.38 kb
/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << '\n'
#define debugsp(x) cerr << #x << " " << x << ' '

using namespace std;

ifstream in ("zoo.in");
ofstream out ("zoo.out");

const int INF = 2e9;

struct Point {
    int x, y, type, qpos, ipos;

    bool operator < (const Point &aux) const {
        if (x == aux.x) {
            if (y == aux.y)
                return type < aux.type;
            return y < aux.y;
        }
        return x < aux.x;
    }
};

struct Query {
    pair <int, int> st_jos, dr_sus;
    int st_jos_ans, dr_sus_ans;
};

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) {
            for (int i = pos; i <= _n; i += lsb(i))
                a[i]++;
        }

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

vector <int> normalize_array (const vector <int> &v) {
    vector <int> idx(v.size()), ret(v.size());

    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&v](int i, int j) {
        return v[i] < v[j];
    });

    ret[idx[0]] = 1;
    for (size_t i = 1; i < v.size(); i++)
        ret[idx[i]] = ret[idx[i - 1]] + (v[idx[i]] != v[idx[i - 1]]);
    
    return ret;
}

void solve(int n, int m, const vector <Point> &v, vector <Query> &q) {
    Fenwick aib(n + 2 * m + 2);

    for (auto it : v) {
        //debugsp(it.x); debugsp(it.y); debug(it.type);
        if (it.type == 1)
            aib.Update(it.y);
        else {
            //debug(it.qpos);
            int l, r;
            l = it.y;

            if (it.type == 0)
                r = q[it.qpos].dr_sus.second;
            else r = q[it.qpos].st_jos.second;

            if (l > r)
                swap(l, r);

            //debugsp(l); debug(r);
            if (it.type == 0)
                q[it.qpos].st_jos_ans = aib.Query(r) - aib.Query(l - 1);
            else
                q[it.qpos].dr_sus_ans = aib.Query(r) - aib.Query(l - 1);
        }
    }
}

int main() {
    int n, m;
    in >> n;

    vector <Point> v(n);
    vector <int> vx, vy;
    map <int, int> mpfirst, mpsecond;
    for (int i = 0; i < n; i++) {
        in >> v[i].x >> v[i].y;
        v[i].type = 1; // punct
        v[i].ipos = i;

        vx.push_back(v[i].x);
        vy.push_back(v[i].y);
    }
    
    in >> m;
    v.resize(n + 2 * m);
    vector <Query> q(m);
    for (int i = 0; i < m; i++) {
        int j = 2 * i + n;
        in >> v[j].x >> v[j].y; v[j].type = 0; // st_jos
        in >> v[j + 1].x >> v[j + 1].y; v[j + 1].type = 2; // dr_sus

        vx.push_back(v[j].x); vx.push_back(v[j + 1].x);
        vy.push_back(v[j].y); vy.push_back(v[j + 1].y);
        v[j].qpos = v[j + 1].qpos = i;
        v[j].ipos = j;
    }

    vx = normalize_array(vx);
    vy = normalize_array(vy);

    for (int i = 0; i < n + 2 * m; i++) {
        v[i].x = vx[i];
        v[i].y = vy[i];
    }

    for (int i = 0; i < m; i++) {
        int j = 2 * i + n;
        
        q[i].st_jos = make_pair(v[j].x, v[j].y); 
        q[i].dr_sus = make_pair(v[j + 1].x, v[j + 1].y);
    }
    
    //for (auto it : v)
    //    cerr << it.x << ' ' << it.y << '\n';
    sort(v.begin(), v.end());

    solve(n, m, v, q);

    for (auto it : q)
        out << it.dr_sus_ans - it.st_jos_ans << '\n';
    in.close();
    out.close();
    return 0;
}