Canadian Computing Competition: 2014 Stage 1, Senior #4
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 Specification
The first line of input is the integer ~N~ (
~1 \le N \le 1\,000~), the number of pieces of glass. The second line of input is the integer ~T~ (
~1 \le T \le 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 \le t_i \le 1\,000\,000~. The top-most, left-most coordinate where glass can be placed is 
~(0, 0)~ and you may assume 
~0 \le x_l < x_r \le K~ and 
~0 < y_t < y_b \le K~.
The following additional constraints will apply.
- At least 10% of the marks will be for test cases where
~N \le 100~ and 
~K \le 100~;
- at least 30% of the marks will be for test cases where
~N \le 1\,000~ and 
~K \le 1\,000~;
- at least 40% of the marks will be for test cases where ~N \le 100~ and
~K \le 1\,000\,000\,000~;
- the remaining marks will be for test cases where ~N \le 1\,000~ and ~K \le 1\,000\,000\,000~.
Output Specification
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 Input
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 Input
5
Explanation of Output for Sample Input
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.
Comments
Can someone help me with test case 9? Is my data structure not correct?
You don't need BigIntegers at all. Just use a long.
Not really a big deal, but I'm pretty sure y
should be greater than or equal to 0, since the topmost coordinate is (0, 0).
This comment is hidden due to too much negative feedback. Show it anyway.
If this is a CCC question why is SourSpinach listed as the author?
He actually authored this problem, along with others (such as some of the FHC problems).