CCC '14 S4 - Tinted Glass Window

View as PDF
Submit solution
Points: 15 (partial)
Time limit: 1.0s
Memory limit: 256M
Author:
SourSpinach
Problem types
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 ith 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


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

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


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

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


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

    Input Specification

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


  • -12
    aaronhe07  commented on July 29, 2020, 3:24 a.m. ← edited

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


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

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


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

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