Solution for spoj.pl/problems/INTEST/

#include <algorithm>
#include <numeric>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct brick{
    int x1,x2,y1,y2,id;
    brick(int x1, int y1, int x2, int y2, int id):x1(x1),y1(y1),x2(x2),y2(y2),id(id){}
    brick():id(-1){}
};

bool by_x(const brick& a, const brick& b){
    return a.x1 < b.x1;
}

bool by_y(const brick& a, const brick& b){
    if (a.y2 != b.y2) return a.y2<b.y2;
    else return a.x1<b.x1;
}

map<int, vector<brick> > h;
brick bricks[100005];

int p[100005], rk[100005];

int getp(int u){
    if (p[u] != u) p[u]=getp(p[u]);
    return p[u];
}

bool merge(int u, int v){
    int pu=getp(u), pv=getp(v);
    if (pu == pv) return false;
    if (rk[pu] < rk[pv]){
        p[pu]=pv;
    } else {
        p[pv]=pu;
        if (rk[pu] == rk[pv]) ++rk[pu];
    }
    return true;
}

int main() {
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; ++i){
        rk[i]=1; p[i]=i;
        int x1, x2, y1, y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        if (x1>x2) swap(x1,x2); if (y1>y2) swap(y1,y2);
        bricks[i] = brick(x1,y1,x2,y2,i);
        h[y2].push_back(bricks[i]);
    }
    for(map<int,vector<brick> >::iterator it=h.begin(); it != h.end(); ++it) sort(it->second.begin(),it->second.end(),by_x);
    sort(bricks,bricks+n,by_y);
    int res=n;

    for(int i=0; i<n; ++i){
        vector<brick> &v = h[bricks[i].y1];
        if (v.size() == 0) continue;
        int sz = v.size();
        if (v[0].x1 >= bricks[i].x2 || v[sz-1].x2 <= bricks[i].x1) continue;
        int L = 0;
        if (v[0].x2 <= bricks[i].x1){
            int r=sz-1;
            while (L+1<r){
                int m=(L+r)/2;
                if (v[m].x2 <= bricks[i].x1) L=m; else r=m;
            }
            L=r;
        }
        int R = sz-1;
        if (v[R].x1 >= bricks[i].x2){
            int l=0;
            while (l+1<R){
                int m=(l+R)/2;
                if (v[m].x1 >= bricks[i].x2) R=m; else l=m;
            }
            R=l;
        }
        for (int j=L; j<=R; ++j) if (merge(bricks[i].id,v[j].id)) --res;
    }
    printf("%d",res);
}