Paint Bucket Areas
National Olympiad — Regional round (2017 season)
Submission name: paint.cpp
Problem summary
Nonintersecting rectangle contours divide a rectangular canvas into regions. For each independent bucket-fill query at a white point, find the area of its region; the fill is reset before the next query.
Input
Canvas width height; N; N rectangles x y width height; T; T query points.
Output
One region area per query.
Constraints
All input integers are positive and at most 11000; contours have no common points; query points are in white regions.
Worked example
An independently prepared example for this explanation.
Input
11 7 3 2 1 5 5 8 2 2 3 3 2 3 2 4 4 3 3 5 10 1 9 3
Output
6 19 46 6
Solution analysis
- Contours form a containment forest because rectangles cannot cross. Treat the canvas as a root rectangle. The region immediately inside any rectangle is its area minus the full areas of its immediate child rectangles; deeper descendants are already excluded by their enclosing child.
- Sweep rectangle sides and query points in increasing x. A map of horizontal boundary heights stores the innermost active rectangle immediately below each boundary. Opening rectangle i identifies its parent from that map, subtracts area[i] from its parent’s region area, and inserts its top/bottom markers. Closing erases both markers. A query looks up its innermost containing rectangle.
- The sample’s 5×5 rectangle contains a 3×2 child, so its own region has area 25−6=19. The canvas exterior region has area 77−25−6=46. The child and the separate 2×3 rectangle each have area 6. Queries may occur before all children are discovered, so save their region identities and print areas only after the sweep finishes.
Why it works
The map invariant follows because each opening replaces a vertical interval of the parent with the new innermost rectangle, and a closing removes it after all active descendants have closed. Thus parent links and query identities are exact. Removing each immediate child’s area precisely once leaves exactly the points reachable inside the parent without crossing a contour, proving each reported area.
Watch out. Subtract immediate children rather than every descendant. Each fill is reset, so queries do not change geometry. Queries cannot lie on drawn contours.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
// Algorithm: Contours form a containment forest because rectangles cannot cross.
using namespace std;
struct Event{
int x,y,bottom,type,id;
bool operator<(const Event&other)const{
if(x!=other.x){
return x<other.x;
}
return type<other.type;
}
};
int main(){
int width,height,n;
cin>>width>>height>>n;
vector<long long>area(n+1);
area[0]=1LL*width*height;
vector<Event>events;
for(int i=1;i<=n;++i){
int x,y,w,h;
cin>>x>>y>>w>>h;
area[i]=1LL*w*h;
events.push_back({x,y,y+h,1,i});
events.push_back({x+w,y,y+h,-1,i});
}
int queries;
cin>>queries;
vector<int>region(queries);
for(int i=0;i<queries;++i){
int x,y;
cin>>x>>y;
events.push_back({x,y,0,0,i});
}
sort(events.begin(),events.end());
map<int,int>active;
active[-1]=0;
for(auto event:events){
if(event.type==-1){
active.erase(event.y);
active.erase(event.bottom);
}
else if(event.type==1){
int parent=prev(active.upper_bound(event.y))->second;
area[parent]-=area[event.id];
active[event.y]=event.id;
active[event.bottom]=parent;
}
else{
region[event.id]=prev(active.upper_bound(event.y))->second;
}
}
for(int id:region){
cout<<area[id]<<'\n';
}
}