Cod sursa(job #2579370)

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

class Parser {
  private:
    static const int SIZE = 1e5;
    char str[SIZE];

    int ptr;
    FILE *fin;

    char getChar() {
        if (ptr == SIZE) {
            fread(str, sizeof(char), SIZE, fin);
            ptr = 0;
        }
        return str[ptr++];
    }

    int getInt() {
        char chr = getChar();
        while (!isdigit(chr) && chr != '-')
            chr = getChar();
        int sgn = +1;
        if (chr == '-') {
            sgn = -1;
            chr = getChar();
        }
        int nr = 0;
        while (isdigit(chr)) {
            nr = nr * 10 + chr - '0';
            chr = getChar();
        }
        return nr * sgn;
    }

  public:
    Parser(const char* str) :
        ptr(SIZE), fin(fopen(str, "r")) { }

    ~Parser() {
        fclose(fin);
    }

    friend Parser& operator>>(Parser& in, int& nr) {
        nr = in.getInt();
        return in;
    }
};

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