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:
