D - Suddenly, A Tempest Editorial by balakrishnan_v


Lets maintain a set of rectangles at each time. Each operation either moves the rectangle or splits the rectangle into two each of which move in different directions. Since N is small, we can simply keep all rectangles. In the end, we construct a graph which connects two touching rectangles. We can easily check if two rectangles are touching by moving one rectangle in either of the 4 cardinal directions and seeing if there is an overlap. The desired output is a sorted list of sum of the rectangle areas within each connected component

C++

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct Rect {
    int x1, y1, x2, y2;
};
ll dfs(int u, const vector<set<int>>& E, vector<bool>& visited, const vector<Rect>& rects) {
    visited[u] = true;
    ll area = (ll)(rects[u].x2 - rects[u].x1 + 1) * (rects[u].y2 - rects[u].y1 + 1);
    for(int v : E[u]) {
        if (!visited[v]) {
            area += dfs(v, E, visited, rects);
        }
    }
    return area;
}

int main() {
    int N,X,Y;
    cin >> N >> X >> Y;

    vector<Rect> rects;
    rects.push_back({0, 0, X-1, Y-1});

    for(int i=0;i<N;i++) {
        string s;
        cin>>s;
        int a,b;
        cin>>a>>b;
        
        vector<Rect> new_rects;
        if (s[0]=='X') {
            for(const Rect& rect : rects) {
                if (rect.x2 < a) {
                    // whole rectangle changes
                    // y gets subtracted by b
                    new_rects.push_back({rect.x1, rect.y1 - b, rect.x2, rect.y2 - b});
                } else if (rect.x1 >= a) {
                    new_rects.push_back({rect.x1, rect.y1 + b, rect.x2, rect.y2 + b});
                } else {
                    // x1 to a-1
                    // a to x2
                    new_rects.push_back({rect.x1, rect.y1 - b, a - 1, rect.y2 - b});
                    new_rects.push_back({a, rect.y1 + b, rect.x2, rect.y2 + b});
                }
            }
        } else {
            for(const Rect& rect : rects) {
                if (rect.y2 < a) {
                    // whole rectangle changes
                    // y gets subtracted by b
                    new_rects.push_back({rect.x1 - b, rect.y1, rect.x2 - b, rect.y2});
                } else if (rect.y1 >= a) {
                    new_rects.push_back({rect.x1 + b, rect.y1, rect.x2 + b, rect.y2});
                } else {
                    // y1 to a-1
                    // a to y2
                    new_rects.push_back({rect.x1 - b, rect.y1, rect.x2 - b, a - 1});
                    new_rects.push_back({rect.x1 + b, a, rect.x2 + b, rect.y2});
                }
            }
        }
        swap(rects, new_rects);
    }

    int m = rects.size();
    vector<set<int>> E(rects.size());
    for(int i=0;i<rects.size();i++) {
        auto& rect = rects[i];
        int dx[]={-1,1,0,0};
        int dy[]={0,0,-1,1};
        for(int dir=0;dir<4;dir++) {
            int nx1 = rect.x1 + dx[dir];
            int ny1 = rect.y1 + dy[dir];
            int nx2 = rect.x2 + dx[dir];
            int ny2 = rect.y2 + dy[dir];

            for(int j=0;j<rects.size();j++) {
                if (i==j) continue;
                auto& orect = rects[j];
                
                int ix1 = max(nx1, orect.x1);
                int iy1 = max(ny1, orect.y1);
                int ix2 = min(nx2, orect.x2);
                int iy2 = min(ny2, orect.y2);
                if (ix1 <= ix2 && iy1 <= iy2) {
                    E[i].insert(j);
                }
            }
        }
    }
    
    vector<bool> visited(m, false);
    vector<ll> ans;
    for(int i=0;i<m;i++) {
        if (visited[i]) continue;
        ans.push_back(dfs(i, E, visited, rects));
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << "\n";
    for(ll a : ans) {
        cout << a << " ";
    }
    cout << "\n";
    return 0;
}

posted:
last update: