## CCC '14 S4 - Tinted Glass Window

View as PDF

Points: 15 (partial)
Time limit: 2.0s
Memory limit: 64M

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 co-ordinate where glass can be placed is and you may assume and , 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. • bobhob314  commented on Nov. 11, 2015, 9:43 p.m.

Any hints on why I'm getting RTE?

• bobhob314  commented on Jan. 28, 2015, 2:44 p.m.

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

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

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

• bobhob314  commented on Jan. 28, 2015, 7:25 p.m.

Who is this kind fellow? And what is this FHC?

EDIT: Oh nvm about the FHC part. What is Foxen?

MOD EDIT: Double post merged.