Submission #70977870

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
struct rect{
    int x1,y1,x2,y2;
};
int fa[N],sz[N];
int fi(int x){
	return fa[x]==x?x:fa[x]=fi(fa[x]);
}
bool chk(int l1,int r1,int l2,int r2){
	return max(l1,l2)<=min(r1,r2);
}
signed main(){
	ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(0);
    vector<rect>v;
    int n,x,y;
    cin>>n>>x>>y;
    v.push_back({0,0,x-1,y-1});
    for(int o=1;o<=n;o++){
        char c;int a,b;
        cin>>c>>a>>b;
        vector<rect>vv;
        if(c=='X'){
            for(auto [x1,y1,x2,y2]:v){
                if(x1>=a){
                    y1+=b,y2+=b;
                    vv.push_back({x1,y1,x2,y2});
                }else if(x2<a){
                    y1-=b,y2-=b;
                    vv.push_back({x1,y1,x2,y2});
                }else{
                    vv.push_back({x1,y1-b,a-1,y2-b});
                    vv.push_back({a,y1+b,x2,y2+b});
                }
            }
        }
        else{
            for(auto [x1,y1,x2,y2]:v){
                if(y1>=a){
                    x1+=b,x2+=b;
                    vv.push_back({x1,y1,x2,y2});
                }
                else if(y2<a){
                    x1-=b,x2-=b;
                    vv.push_back({x1,y1,x2,y2});
                }
                else{
                    vv.push_back({x1-b,y1,x2-b,a-1});
                    vv.push_back({x1+b,a,x2+b,y2});
                }
            }
        }
        v.swap(vv);
    }
    int l=v.size();
    for(int i=0;i<l;i++) fa[i]=i,sz[i]=(v[i].y2-v[i].y1+1)*(v[i].x2-v[i].x1+1);
    for(int i=0;i<l;i++){
        for(int j=0;j<l;j++){
            bool flag=0;
            if(v[i].y1==v[j].y2+1&&chk(v[i].x1,v[i].x2,v[j].x1,v[j].x2)) flag=1;
            if(v[i].y2+1==v[j].y1&&chk(v[i].x1,v[i].x2,v[j].x1,v[j].x2)) flag=1;
            if(v[i].x1==v[j].x2+1&&chk(v[i].y1,v[i].y2,v[j].y1,v[j].y2)) flag=1;
            if(v[i].x2+1==v[j].x1&&chk(v[i].y1,v[i].y2,v[j].y1,v[j].y2)) flag=1;
            if(flag){
				int x=fi(i),y=fi(j);
                if(x^y) fa[x]=y,sz[y]+=sz[x];
            }
        }
    }
    vector<int>ans;
    for(int i=0;i<l;i++) if(fa[i]==i) ans.push_back(sz[i]);
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<"\n";
    for(int x:ans) cout<<x<<" ";
    cout<<"\n";
    return 0;
}

Submission Info

Judge Result