class Solution {
public:
    #define LSB(x) (x&(-x))
    #define MAX 100000

    int AIB1[MAX], AIB2[MAX];

    void update1(int pos, int val) {
        while (pos < MAX) {
            AIB1[pos] += val;
            pos += LSB(pos);
        }
    }

    void update2(int pos, int val) {
        while (pos < MAX) {
            AIB2[pos] += val;
            pos += LSB(pos);
        }
    }

    void add(int l, int r, int val) {
        update1(l, val);
        update1(r+1, -val);

        update2(l, val*(l-1));
        update2(r+1, -val*r);
    }

    int queryAux1(int pos) {
        int sum = 0;
        if (pos <= 0) return 0;
        while (pos) {
            sum += AIB1[pos];
            pos -= LSB(pos);
        }
        return sum;
    }

    int queryAux2(int pos) {
        int sum = 0;
        if (pos <= 0) return 0;
        while (pos) {
            sum += AIB2[pos];
            pos -= LSB(pos);
        }
        return sum;
    }

    int queryAux(int x) {
        return queryAux1(x)*x - queryAux2(x);
    }

    int query(int l, int r) {
        return queryAux(r) - queryAux(l-1);
    }

    bool isRectangleCover(vector<vector<int>>& rectangles) {
        if (rectangles.size() == 0) {
            return false;
        }

        memset(AIB1, 0, sizeof(AIB1));
        memset(AIB2, 0, sizeof(AIB2));

        int mm = 1;
        for (int i = 0; i < rectangles.size(); i++) {
            mm = min(mm, rectangles[i][1]);
        }
        if (mm < 0) {
            mm = -mm; mm++;
        } else {
            mm = 1;
        }

        for (int i = 0; i < rectangles.size(); i++) {
            rectangles[i][1] += mm;
            rectangles[i][3] += mm;
        }

        map<int, vector<pair<pair<int, int>, int>>> H;
        for (int i = 0; i < rectangles.size(); i++) {
            H[rectangles[i][0]].push_back({{rectangles[i][1], rectangles[i][3]}, +1});
            H[rectangles[i][2]].push_back({{rectangles[i][1], rectangles[i][3]}, -1});
        }

        unordered_set<int> Hstart, Hend;

        for (auto it = H.begin(); it != H.end(); it++) {
            for (auto it2 = it->second.begin(); it2 != it->second.end(); it2++) {
                if (it2->second == -1) {
                    add(it2->first.first, it2->first.second, -1);
                    Hstart.erase(Hstart.find(it2->first.first));
                    Hend.erase(Hend.find(it2->first.second));
                }
            }

            for (auto it2 = it->second.begin(); it2 != it->second.end(); it2++) {
                if (it2->second == +1) {
                    int sum = query(it2->first.first, it2->first.second);
                    if (sum > 2) {
                        return false;
                    } else if (sum == 2) {
                        if (Hstart.find(it2->first.second) == Hstart.end() || Hend.find(it2->first.first) == Hend.end()) {
                            return false;
                        }
                    } else if (sum == 1) {
                        if (Hstart.find(it2->first.second) == Hstart.end() && Hend.find(it2->first.first) == Hend.end()) {
                            return false;
                        }
                    }
                    add(it2->first.first, it2->first.second, +1);
                    Hstart.insert(it2->first.first);
                    Hend.insert(it2->first.second);
                }
            }
        }

        int lmin = rectangles[0][0];
        int lmax = rectangles[0][2];
        int cmin = rectangles[0][1];
        int cmax = rectangles[0][3];
        int area = 0;
        for (int i = 0; i < rectangles.size(); i++) {
            lmin = min(lmin, rectangles[i][0]);
            lmax = max(lmax, rectangles[i][2]);
            cmin = min(cmin, rectangles[i][1]);
            cmax = max(cmax, rectangles[i][3]);

            area += (rectangles[i][2] - rectangles[i][0]) * (rectangles[i][3] - rectangles[i][1]);
        }

        if (area != (lmax - lmin) * (cmax - cmin)) {
            return false;
        }

        return true;
    }
};