Cod sursa(job #2579363)

Utilizator IulianOleniucIulian Oleniuc IulianOleniuc Data 12 martie 2020 13:21:58
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <bits/stdc++.h>
using namespace std;

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

class FenTree {
  private:
    int n;
    vector<int> bit;

  public:
    FenTree(int n) :
        n(n), bit(n + 1) { }

    void update(int pos) {
        for (int i = pos; i <= n; i += i & -i)
            bit[i]++;
    }

    int query(int pos) {
        int sum = 0;
        for (int i = pos; i >= 1; i -= i & -i)
            sum += bit[i];
        return sum;
    }

    int query(int left, int right) {
        return query(right) - query(left - 1);
    }
};

struct Tripl {
    int x, y, z;
    Tripl(int x, int y, int z) :
        x(x), y(y), z(z) { }
    inline bool operator<(const Tripl& t) const {
        return x < t.x;
    }
};

struct Entry {
    int t, x, y;
    Entry(int t, int x, int y) :
        t(t), x(x), y(y) { }
    inline int& operator[](int ind) {
        return ind ? y : x;
    }
    inline bool operator<(const Entry& e) const {
        return x < e.x || (x == e.x && (y < e.y || (y == e.y && t < e.t)));
    }
};

int main() {
    vector<Entry> evn;
    vector<Tripl> val;

    int n; fin >> n;
    evn.reserve(n);
    val.reserve(2 * n);
    for (int i = 0; i < n; i++) {
        int x, y; fin >> x >> y;
        evn.emplace_back(0, x, y);
        val.emplace_back(x, evn.size() - 1, 0);
        val.emplace_back(y, evn.size() - 1, 1);
    }

    int q; fin >> q;
    evn.reserve(n + q);
    val.reserve(2 * n + 4 * q);
    for (int i = 1; i <= q; i++) {
        int x1, y1, x2, y2; fin >> x1 >> y1 >> x2 >> y2;
        evn.emplace_back(-i, x1, y1);
        val.emplace_back(x1, evn.size() - 1, 0);
        val.emplace_back(y1, evn.size() - 1, 1);
        evn.emplace_back(+i, x2, y2);
        val.emplace_back(x2, evn.size() - 1, 0);
        val.emplace_back(y2, evn.size() - 1, 1);
    }
    sort(val.begin(), val.end());

    int cnt = 0;
    vector<pair<int, int>> qry(q + 1);
    for (int i = 0; i < (int) val.size(); i++) {
        if (!i || val[i - 1].x != val[i].x)
            cnt++;
        evn[val[i].y][val[i].z] = cnt;
        if (val[i].z == 1) {
            if (evn[val[i].y].t < 0)
                qry[-evn[val[i].y].t].first = cnt;
            else
                qry[+evn[val[i].y].t].second = cnt;
        }
    }
    sort(evn.begin(), evn.end());

    FenTree tree(cnt);
    vector<int> ans(q + 1);
    for (auto& e : evn)
        if (e.t < 0)
            ans[-e.t] -= tree.query(qry[-e.t].first, qry[-e.t].second);
        else if (e.t > 0)
            ans[+e.t] += tree.query(qry[+e.t].first, qry[+e.t].second);
        else
            tree.update(e.y);
    for (int i = 1; i <= q; i++)
        fout << ans[i] << '\n';

    fout.close();
    return 0;
}