The most naive approach to this problem is to simulate applying each coat of paint and then looking at each $1 \times 1$ square to see if it has the right number of coats of paint applied. This approach should get around half credit.

Let us imagine solving the one-dimensional variant of this problem, where we have a fence and can apply coats of paint to some subintervals $[l_i, r_i]$ of the fence. Imagine that we actually had $N$ paint cans and put each can at the location $l_i$ that corresponded to where it started, and we also noted at each location $r_i$ where to stop carrying cans of paint with us. If we then walk along the fence and pick up and drop off cans of paint, at each location in the fence we can count how many coats of paint we would use by counting how many cans of paint we are carrying.

In terms of how to implement this, we can enumerate, for each location, how many cans of paint we're picking up and how many cans of paint we're dropping off. Note, therefore, that the number of coats of paint that are used at location $x$ is equal to the sum of the changes in number of coats of paint that take place over all locations from the beginning to $x$. This technique is often referred to as computing a prefix sum, as we start with an array and then compute the sum of every prefix of the array to get the final result we want.

To apply this to two dimensions, imagine that we take the roof and break it up into 1000 sections, each of which is one-dimensional. We can apply this technique to each section and then sum the results. Code for this is as follows:

#include <bits/stdc++.h> using namespace std; int dp[1000][1001]; int main() { freopen("paintbarn.in", "r", stdin); freopen("paintbarn.out", "w", stdout); int n, k; cin >> n >> k; while(n--) { int a, b, c, d; cin >> a >> b >> c >> d; for(int i = a; i < c; i++) { dp[i][b]++; dp[i][d]--; } } int ret = 0; for(int i = 0; i < 1000; i++) { for(int j = 0; j < 1000; j++) { if(dp[i][j] == k) ret++; dp[i][j+1] += dp[i][j]; } } cout << ret << endl; }

We can do better though - there's no reason that prefix sums only have to work in one dimension! If we have a two-dimension array $g$ and then define $f(i, j)$ to be the sum of all $g(k, l)$ where $k \le i$ and $l \le j$, then we can define $f(i, j) = g(i, j) + f(i-1, j) + f(i, j-1) - f(i-1, j-1)$, and after computing the two-dimension prefix sums, we can iterate over all elements to compute the desired area.

#include <bits/stdc++.h> using namespace std; int dp[1001][1001]; int main() { freopen("paintbarn.in", "r", stdin); freopen("paintbarn.out", "w", stdout); int n, k; cin >> n >> k; while(n--) { int a, b, c, d; cin >> a >> b >> c >> d; dp[a][b]++; dp[a][d]--; dp[c][b]--; dp[c][d]++; } int ret = 0; for(int i = 0; i < 1000; i++) { for(int j = 0; j < 1000; j++) { if(i) dp[i][j] += dp[i-1][j]; if(j) dp[i][j] += dp[i][j-1]; if(i && j) dp[i][j] -= dp[i-1][j-1]; if(dp[i][j] == k) ret++; } } cout << ret << endl; }