Cod sursa(job #2831353)

Utilizator MatteoalexandruMatteo Verzotti Matteoalexandru Data 11 ianuarie 2022 11:07:29
Problema Zoo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.11 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;

    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;
        }
};

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);
    map <int, int> mpfirst, mpsecond;
    for (int i = 0; i < n; i++) {
        in >> v[i].x >> v[i].y;
        v[i].type = 1; // punct
        mpfirst.insert(make_pair(v[i].x, 0));
        mpsecond.insert(make_pair(v[i].y, 0));
    }
    
    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

        v[j].qpos = v[j + 1].qpos = i;

        mpfirst.insert(make_pair(v[j].x, 0));
        mpfirst.insert(make_pair(v[j + 1].x, 0));
        mpsecond.insert(make_pair(v[j].y, 0));
        mpsecond.insert(make_pair(v[j + 1].y, 0));
    }
   
    int cnt = 0;
    for (auto &it : mpfirst)
        it.second = ++cnt;

    cnt = 0;
    for (auto &it : mpsecond)
        it.second = ++cnt;
    
    for (auto &it : v) {
        it.x = mpfirst[it.x];
        it.y = mpsecond[it.y];
    }

    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;
}