## CCC '14 S4 - Tinted Glass Window

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types
##### Canadian Computing Competition: 2014 Stage 1, Senior #4

You are laying 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 -axis or the -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 .

#### Input Specification

The first line of input is the integer (), the number of pieces of glass. The second line of input is the integer (), the threshold for the tint-factor. Each of the next lines contain five integers, representing the position of the top-left and bottom-right corners of the th piece of tinted glass followed by the tint-factor of that piece of glass. Specifically, the integers are placed in the order , where the top-left corner is at and the bottom-right corner is at , and tint-factor is . You can assume that . The top-most, left-most coordinate where glass can be placed is and you may assume and .

The following additional constraints will apply.

• At least 10% of the marks will be for test cases where and ;
• at least 30% of the marks will be for test cases where and ;
• at least 40% of the marks will be for test cases where and ;
• the remaining marks will be for test cases where and .

#### Output Specification

Output the total area of the finished stained glass window which has a tint-factor of at least . All output will be less than , and the output for some test cases will be larger than .

#### 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 and (which has tint-factor of 3, except for a unit square with tint-factor 4), and another region between and (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.

• commented on Feb. 18, 2024, 9:33 p.m.

Can someone help me with test case 9? Is my data structure not correct?

• commented on April 13, 2024, 9:55 p.m.

You don't need BigIntegers at all. Just use a long.

• commented on Nov. 7, 2022, 4:43 p.m. edited

Not really a big deal, but I'm pretty sure should be greater than or equal to , since the topmost coordinate is .

• commented on July 29, 2020, 3:24 a.m. edited

This comment is hidden due to too much negative feedback. Show it anyway.

• commented on Jan. 28, 2015, 7:44 p.m. edited

If this is a CCC question why is SourSpinach listed as the author?

• commented on Jan. 28, 2015, 10:30 p.m.

He actually authored this problem, along with others (such as some of the FHC problems).