Problem S4: Tinted Glass Window

Problem DescriptionCopy Anchor Link

You are laying $N$ rectangular pieces of grey-tinted glass to make a stained glass window. Each piece of glass adds an integer value "tint-factor". Where two pieces of glass overlap, the tint-factor is the sum of their tint-factors.

You know the desired position for each piece of glass and these pieces of glass are placed such that the sides of each rectangle are parallel to either the $x$-axis or the $y$-axis (that is, there are no "diagonal" pieces of glass).

You would like to know the total area of the finished stained glass window with a tint-factor of at least $T$.

Input SpecificationCopy Anchor Link

The first line of input is the integer $N~(1 \leq N \leq 1000)$, the number of pieces of glass. The second line of input is the integer $T~(1 \leq T \leq 1\ 000\ 000 \ 000)$, the threshold for the tint-factor. Each of the next $N$ lines contain five integers, representing the position of the top-left and bottom-right corners of the $i$th piece of tinted glass followed by the tint-factor of that piece of glass. Specifically, the integers are placed in the order $x_l$ $y_t$ $x_r$ $y_b$ $t_i$, where the top-left corner is at $(x_l, y_t)$ and the bottom-right corner is at $(x_r, y_b)$, and tint-factor is $t_i$. You can assume that $1 \leq t_i \leq 1\ 000\ 000$. The top-most, left-most co-ordinate where glass can be placed is $(0,0)$ and you may assume $0\leq x_l < x_r \leq K$ and $0 < y_t < y_b \leq K$, and

The following additional constraints will apply.

• At least 10% of the marks will be for test cases where $N \leq 100$ and $K \leq 100$;

• at least 30% of the marks will be for test cases where $N \leq 1000$ and $K \leq 1000$;

• at least 40% of the marks will be for test cases where $N \leq 100$ and $K \leq 1\ 000 \ 000\ 000$;

• the remaining marks will be for test cases where $N \leq 1000$ and $K \leq 1\ 000 \ 000\ 000$.

Output SpecificationCopy Anchor Link

Output the total area of the finished stained glass window which has a tint-factor of at least $T$. All output will be less than $2^{64}$, and the output for some test cases will be larger than $2^{32}$.

Sample InputCopy Anchor Link

4
3
11 11 20 15 1
13 8 14 17 2
17 8 18 17 1
12 12 19 13 1

Output for Sample InputCopy Anchor Link

5

Explanation of Output for Sample InputCopy Anchor Link

There are 4 pieces of glass used. There are two regions of glass which have a tint-factor greater than or equal to 3: one region between $(13, 11)$ and $(14, 15)$ (which has tint-factor of 3, except for a unit square with tint-factor 4), and another region between $(17,12)$ and $(18,13)$ (with tint-factor 3). In total, these two regions have 5 square units of glass with tint-factor greater than or equal to 3, as shown on the diagram below.