Proficient.
Put your skills to the test.

Problem summary

Rectangle boundaries never touch or cross. Crossing each boundary alternates water and land, with water outside all rectangles. Count the connected land regions.

Source clarification. The PDF’s generic size inequality permits zero width/height, although its island/lake rectangles and nonintersecting contours require positive-area rectangles. The implementation uses that geometric interpretation; zero-area contour semantics are not specified.

Constraints

1 ≤ N ≤ 100000; stated coordinate and size bounds 0…10^9; geometric rectangles have positive area.

Worked example

An independently prepared example for this explanation.

9
0 0 16 14
1 1 8 5
2 2 4 3
11 1 3 7
1 7 8 6
2 8 4 4
3 9 2 2
10 9 5 4
11 10 3 2

4

Solution analysis

1. Disjoint rectangle boundaries imply that rectangles are disjoint or nested. A rectangle at odd nesting depth introduces one land region; one at even depth introduces a lake. Count odd-depth rectangles.
2. Sweep vertical sides from left to right. Maintain a map from horizontal boundary heights to the depth immediately below each height. At a rectangle’s left side, look up the depth at its top coordinate; its own depth is one greater. Insert its top boundary with the new depth and its bottom boundary with the enclosing depth. At its right side erase those two entries.
3. The sample nesting includes an outer island, three additional outer-level land subdivisions inside lakes, and lake boundaries that contribute no region. The sweep counts four odd-depth rectangles. Coincident x event coordinates are harmless for disjoint vertical spans; boundary-contact cases are forbidden.

Why it works

At every sweep x, the map partitions the vertical line into depth-constant intervals. Opening a rectangle increases depth by one exactly between its top and bottom, while closing restores the enclosing interval. Because no boundaries cross, active descendants cannot extend beyond a closing ancestor. Thus every recorded depth is its actual nesting depth. Alternating land and water makes each odd-depth rectangle one distinct connected land component.

Watch out. Counting all rectangles or only outermost rectangles misses islands inside lakes. Endpoint coordinates x+width may reach 2·10^9, so 64-bit coordinates are convenient.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
// Algorithm: Disjoint rectangle boundaries imply that rectangles are disjoint or nested.
using namespace std;
struct Event{
    long long x,top,bottom;
    int type;
    bool operator<(const Event&other)const{
        if(x!=other.x){
            return x<other.x;
        }
        return type<other.type;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<Event>events;
    for(int i=0;i<n;++i){
        long long x,y,width,height;
        cin>>x>>y>>width>>height;
        events.push_back({x,y,y+height,1});
        events.push_back({x+width,y,y+height,-1});
    }
    sort(events.begin(),events.end());
    map<long long,int>depth;
    depth[-1]=0;
    int answer=0;
    for(auto event:events){
        if(event.type==-1){
            depth.erase(event.top);
            depth.erase(event.bottom);
        }
        else{
            int enclosing=prev(depth.upper_bound(event.top))->second;
            int current=enclosing+1;
            if(current%2==1){
                ++answer;
            }
            depth[event.top]=current;
            depth[event.bottom]=enclosing;
        }
    }
    cout<<answer<<'\n';
}