Submission #70996579

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
 
#define int long long

struct rectangle{
    int topX,bottomX,leftY,rightY;
    rectangle(int t,int b,int l,int r):topX(t),bottomX(b),leftY(l),rightY(r){}
    optional<pair<rectangle,rectangle>> breakX(int A,int B){
        if(bottomX>=A){
            leftY+=B;
            rightY+=B;
            return nullopt;
        } else if(topX<A){
            leftY-=B;
            rightY-=B;
            return nullopt;
        }
        rectangle niche = {A-1,bottomX,leftY,rightY};
        rectangle uppar = {topX,A,leftY,rightY};
        niche.breakX(A,B);
        uppar.breakX(A,B);
        return make_pair(niche,uppar);
    }
    optional<pair<rectangle,rectangle>> breakY(int A,int B){
        if(A<=leftY){
            topX+=B;
            bottomX+=B;
            return nullopt;
        } else if(rightY<A){
            topX-=B;
            bottomX-=B;
            return nullopt;
        }
        rectangle left = {topX,bottomX,leftY,A-1};
        rectangle right = {topX,bottomX,A,rightY};
        left.breakY(A,B);
        right.breakY(A,B);
        return make_pair(left,right);
    }
    bool fuck(rectangle &other){
        if(rightY+1==other.leftY){
            if(min(topX,other.topX)>=max(bottomX,other.bottomX))return true;
        }
        if(topX+1==other.bottomX){
            if(min(rightY,other.rightY)>=max(leftY,other.leftY))return true;
        }
        return false;
    }
    int sussy(){
        return (rightY-leftY+1)*(topX-bottomX+1);
    }
};

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N,X,Y;
    cin >> N >> X >> Y;
    vector<rectangle> rect;
    rect.emplace_back(X-1,0,0,Y-1);
    for(int i=1;i<=N;i++){
        char C;int A,B;cin>>C>>A>>B;
        vector<rectangle> rect2;
        if(C=='X'){
            for(auto&xxx:rect){
                auto t = xxx.breakX(A,B);
                if(!t)rect2.emplace_back(xxx);
                else {
                    rect2.emplace_back(t->first);
                    rect2.emplace_back(t->second);
                }
            }
        } else {
            for(auto&xxx:rect){
                auto t = xxx.breakY(A,B);
                if(!t)rect2.emplace_back(xxx);
                else {
                    rect2.emplace_back(t->first);
                    rect2.emplace_back(t->second);
                }
            }
        }
        swap(rect,rect2);
    }
    N = rect.size();
    vector<bool> visited(N);
    vector<int> ans;
    auto dfs = [&](auto&& self,int x)->void{
        visited[x]=true;
        ans.back()+=rect[x].sussy();
        for(int i=0;i<N;i++)if(!visited[i] and (rect[x].fuck(rect[i]) or rect[i].fuck(rect[x])))self(self,i);
    };
    for(int i=0;i<N;i++)if(!visited[i]){
        ans.emplace_back(0);
        dfs(dfs,i);
    }
    sort(ans.begin(),ans.end());
    cout << ans.size() << '\n';
    for(int&i:ans)cout<<i<<' ';
}

Submission Info

Judge Result