## CCC '14 S4 - Tinted Glass Window

View as PDF

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

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
##### 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 .

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 July 28, 2020, 11:24 p.m.

This comment is hidden due to too much negative feedback. Click here to view it.

• commented on Nov. 11, 2015, 9:43 p.m.

Any hints on why I'm getting RTE?

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

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

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

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

• 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.