Painting the Barn (Silver) (Editorial)

First, let's consider the one-dimensional version of the problem. Suppose we have $n$ segments [a_i, b_i] on a number line, where 0 \le a_i, b_i \le 1000. The goal is to determine how many segments cover each integer on this line.

We declare an integer array dp and initialize it with zeros. Then, for each segment [a_i, b_i], perform two operations:

Next, compute the prefix sums of the $dp$ array. The value of $dp[i]$ represents the number of segments that cover the number $i$.

For example, consider the following set of segments: [3; 7], [6; 9], [1; 4], [3; 8], [2; 5]. Initialize the $dp$ array:

For each segment [a_i, b_i], perform the following two operations: dp[a_i]++; dp[b_i + 1]--.

Now let's consider the two-dimensional version of the problem. Suppose we have $n$ rectangles on a plane, each defined by coordinates (x_1, y_1) - (x_2, y_2)~(0 \le x_1, y_1, x_2, y_2 \le 1000). The goal is to determine how many rectangles cover each cell of the plane.

Declare a two-dimensional integer array $dp$ and initialize it with zeros. Then, for each rectangle (x_1, y_1) - (x_2, y_2), perform the following four operations:

After that, compute the prefix sums in the $dp$ array. The value of dp[i][j] represents the number of rectangles that contain the cell $(i,j)$.

For example, consider the rectangle (2, 2) - (4, 5).

Example

Let’s consider the given example containing three rectangles.

$8$ squares are covered with exactly $2$ layers of paint.

Algorithm implementation

Declare a two-dimensional array $dp$.

#define MAX 1001
int dp[MAX][MAX];

Read the input data.

scanf("%d %d", &n, &k);
while (n--)
{

For each rectangle (a, b) - (c, d), perform the following four operations.

  scanf("%d %d %d %d", &a, &b, &c, &d);
  dp[a][b]++;
  dp[a][d]--;
  dp[c][b]--;
  dp[c][d]++;
}

Count the number of wall cells covered with exactly $k$ layers of paint in the variable $res$.

res = 0;

Compute the prefix sums in the $dp$ array.

for (i = 0; i < MAX; i++)
  for (j = 0; j < MAX; 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 the cell $(i,j)$ is covered with $k$ layers of paint, increment $res$ by $1$.

    if (dp[i][j] == k) res++;
  }

Print the answer.

printf("%d\n", res);