src/test/yosupo_area_of_union_of_rectangles.cpp

• View this file on GitHub
• Last update: 2026-03-17 19:58:42+09:00
• Problem: https://judge.yosupo.jp/problem/area_of_union_of_rectangles

Depends on

• src/segtree/lazy_segtree.hpp
• src/template.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/area_of_union_of_rectangles"
#include "../segtree/lazy_segtree.hpp"

struct UnionRect{
    struct S{
        int c, w;
        static S op(S x, S y){
            if(x.c<y.c)return x;
            if(x.c>y.c)return y;
            return {x.c,x.w+y.w};
        };
        static S e(){
            return {(int)1e9,0};
        }
    };
    struct F{
        int a;
        static S mpp(F f, S x){
            x.c+=f.a;
            return x;
        }
        static F cmpo(F f, F g){
            g.a+=f.a;
            return g;
        }
        static F id(){
            return {0};
        }
    };

    vector<array<int,4>> a;
    vector<int> z;
    void add(int d, int u, int l, int r){
        a.push_back({d,u,l,r});
        z.push_back(l);
        z.push_back(r);
    }
    long area(){
        int n=si(a);
        if(n==0)return 0;
        sort(all(z));
        z.erase(unique(all(z)),z.end());
        vector<array<int,4>> ev;
        rep(i,n){
            int l=lower_bound(all(z),a[i][2])-z.begin();
            int r=lower_bound(all(z),a[i][3])-z.begin();
            ev.push_back({a[i][0],l,r,0});
            ev.push_back({a[i][1],l,r,1});
        }
        sort(all(ev));
        int pr=0;
        int M=si(z);
        lazy_segtree<S,S::op,S::e,F,F::mpp,F::cmpo,F::id> seg(M-1);
        rep(i,M-1)seg.set(i,S{0,z[i+1]-z[i]});
        
        int W=z.back()-z[0];
        long ret=0;
        int cur=W;
        for(auto [h,l,r,v]:ev){
            ret+=1l*(h-pr)*(W-cur);
            if(v==0){
                S s=seg.prod(l,r);
                if(s.c==0)cur-=s.w;
                seg.apply(l,r,{1});
            }
            else{
                S s=seg.prod(l,r);
                if(s.c==1)cur+=s.w;
                seg.apply(l,r,{-1});
            }
            pr=h;
        }
        return ret;
    }
};

int main(){
    int N;
    cin>>N;
    UnionRect ur;
    rep(i,N){
        int l,d,r,u;
        cin>>l>>d>>r>>u;
        ur.add(l,r,d,u);
    }
    cout<<ur.area()<<"\n";
}

#line 1 "src/test/yosupo_area_of_union_of_rectangles.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/area_of_union_of_rectangles"
#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(int)(n);++i)
template<typename S,typename F> bool chmin(S&a,F b){return b<a?(a=b,1):0;}
template<typename S,typename F> bool chmax(S&a,F b){return b>a?(a=b,1):0;}
bool _=(ios::sync_with_stdio(0),cin.tie(0),cout<<fixed<<setprecision(16),0);
#line 3 "src/segtree/lazy_segtree.hpp"

template<class S,auto op,auto e,class F,auto mpp,auto cmpo,auto id>
class lazy_segtree {
    int n,log;
    vector<S> d;
    vector<F> lz;
    void update(int k){d[k]=op(d[k*2],d[k*2+1]);}
    void all_apply(int k,F f){
        d[k]=mpp(f,d[k]);
        if(k<n) lz[k]=cmpo(f,lz[k]);
    }
    void push(int k){
        all_apply(k*2,lz[k]);
        all_apply(k*2+1,lz[k]);
        lz[k]=id();
    }
    void UPDATE(int k){
        for(int i=1;i<log;i++) update(k>>i);
    }
    void PUSH(int k){
        for(int i=log;--i;) push(k>>i);
    }
public:
    lazy_segtree(int n):lazy_segtree(vector<S>(n,e())){}
    lazy_segtree(vector<S> a){
        n=log=1;
        while(n<si(a)) n<<=1,log++;
        d.resize(2*n,e());
        lz.resize(2*n,id());
        rep(i,si(a))d[n+i]=a[i];
        for(int i=n;--i;) update(i);
    }
    void set(int p,S x){
        p+=n;
        PUSH(p);
        d[p]=x;
        UPDATE(p);
    }
    S get(int p){
        p+=n;
        PUSH(p);
        return d[p];
    }
    S prod(int l,int r){
        if(l>=r) return e();
        l+=n,r+=n;
        for(int i=log;--i;){
            if((l>>i)<<i!=l) push(l>>i);
            if((r>>i)<<i!=r) push((r-1)>>i);
        }
        S sl=e(),sr=e();
        for(;l<r;l>>=1,r>>=1){
            if(l&1) sl=op(sl,d[l++]);
            if(r&1) sr=op(d[--r],sr);
        }
        return op(sl,sr);
    }
    void apply(int p,F f){
        p+=n;
        PUSH(p);
        d[p]=mpp(f,d[p]);
        UPDATE(p);
    }
    void apply(int l,int r,F f){
        if(l>=r) return;
        l+=n,r+=n;
        for(int i=log;--i;){
            if((l>>i)<<i!=l) push(l>>i);
            if((r>>i)<<i!=r) push((r-1)>>i);
        }
        int ml=l,mr=r;
        for(;l<r;l>>=1,r>>=1){
            if(l&1) all_apply(l++,f);
            if(r&1) all_apply(--r,f);
        }
        l=ml,r=mr;
        for(int i=1;i<log;i++){
            if((l>>i)<<i!=l) update(l>>i);
            if((r>>i)<<i!=r) update((r-1)>>i);
        }
    }
};
#line 3 "src/test/yosupo_area_of_union_of_rectangles.cpp"

struct UnionRect{
    struct S{
        int c, w;
        static S op(S x, S y){
            if(x.c<y.c)return x;
            if(x.c>y.c)return y;
            return {x.c,x.w+y.w};
        };
        static S e(){
            return {(int)1e9,0};
        }
    };
    struct F{
        int a;
        static S mpp(F f, S x){
            x.c+=f.a;
            return x;
        }
        static F cmpo(F f, F g){
            g.a+=f.a;
            return g;
        }
        static F id(){
            return {0};
        }
    };

    vector<array<int,4>> a;
    vector<int> z;
    void add(int d, int u, int l, int r){
        a.push_back({d,u,l,r});
        z.push_back(l);
        z.push_back(r);
    }
    long area(){
        int n=si(a);
        if(n==0)return 0;
        sort(all(z));
        z.erase(unique(all(z)),z.end());
        vector<array<int,4>> ev;
        rep(i,n){
            int l=lower_bound(all(z),a[i][2])-z.begin();
            int r=lower_bound(all(z),a[i][3])-z.begin();
            ev.push_back({a[i][0],l,r,0});
            ev.push_back({a[i][1],l,r,1});
        }
        sort(all(ev));
        int pr=0;
        int M=si(z);
        lazy_segtree<S,S::op,S::e,F,F::mpp,F::cmpo,F::id> seg(M-1);
        rep(i,M-1)seg.set(i,S{0,z[i+1]-z[i]});
        
        int W=z.back()-z[0];
        long ret=0;
        int cur=W;
        for(auto [h,l,r,v]:ev){
            ret+=1l*(h-pr)*(W-cur);
            if(v==0){
                S s=seg.prod(l,r);
                if(s.c==0)cur-=s.w;
                seg.apply(l,r,{1});
            }
            else{
                S s=seg.prod(l,r);
                if(s.c==1)cur+=s.w;
                seg.apply(l,r,{-1});
            }
            pr=h;
        }
        return ret;
    }
};

int main(){
    int N;
    cin>>N;
    UnionRect ur;
    rep(i,N){
        int l,d,r,u;
        cin>>l>>d>>r>>u;
        ur.add(l,r,d,u);
    }
    cout<<ur.area()<<"\n";
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	edge_bound_00	AC	7266 ms	67 MB
g++	edge_bound_01	AC	7266 ms	67 MB
g++	edge_bound_02	AC	7292 ms	67 MB
g++	edge_bound_03	AC	7319 ms	67 MB
g++	edge_bound_04	AC	7269 ms	67 MB
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	7689 ms	67 MB
g++	max_random_01	AC	7758 ms	67 MB
g++	max_random_02	AC	7663 ms	67 MB
g++	max_random_03	AC	7729 ms	67 MB
g++	max_random_04	AC	7688 ms	67 MB
g++	random_00	AC	5989 ms	62 MB
g++	random_01	AC	7110 ms	65 MB
g++	random_02	AC	699 ms	11 MB
g++	random_03	AC	6557 ms	63 MB
g++	random_04	AC	4240 ms	57 MB
g++	small_00	AC	11 ms	4 MB
g++	small_01	AC	6 ms	4 MB
g++	small_02	AC	5 ms	4 MB
g++	small_03	AC	16 ms	4 MB
g++	small_04	AC	9 ms	4 MB

Back to top page