850

class Solution {

struct event{
    int x, y1, y2, type;
    event(int x, int type, int y1, int y2):x(x),type(type),y1(y1),y2(y2){}
    bool operator<(const event &a)const{
        if(x != a.x)
            return x < a.x;
        return type < a.type;
    }
};

public:
    int rectangleArea(vector<vector<int>>& rectangles) {
        const int MOD = int(1e9)+7;
        int area = 0;
        multiset<event> events;
        for(auto rec:rectangles){
            events.insert(event(rec[0], 0, rec[1], rec[3]));
            events.insert(event(rec[2], 1, rec[1], rec[3]));
        }

        multiset<pair<int, int>> openEvents;
        int prevX = 0;
        for(auto ev: events){
            int curX = ev.x;
            area = (area + getArea(curX-prevX, openEvents, MOD))%MOD;
            prevX = curX;
            if(ev.type == 1)
                openEvents.erase(openEvents.lower_bound({ev.y1, ev.y2}));
            else
                openEvents.insert({ev.y1, ev.y2});

        }
        return area;
    }

    int getArea(int width, multiset<pair<int, int>> &openEvents, int MOD){
        long int area = 0, bottom = 0;
        for(auto range: openEvents){
            long int top = range.second;
            bottom = max(bottom, long(range.first));
            if(top>bottom)
                area = (area + (width*(top-bottom)))%MOD;
            bottom = max(bottom, top);
        }
        return area;
    }

};