## MEC '16 P6 - Instruments of the Ghostwriters

View as PDF

Points: 10 (partial)
Time limit: 1.4s
Java 8 1.8s
Memory limit: 256M

Author:
Problem types

atarw is playing an excellently-crafted video game made by legolover2 and Hypnova. This game takes place on a by rectangular grid, where is the number of columns and is the number of rows. There are score multipliers each of which are applied to a specific range of columns or rows. These score multipliers stack, i.e. they are applied on the current score, not base score. This means that two score multipliers are equivalent to a single score multiplier. The base score changes depending on the level that atarw is playing on, however the multipliers remain the same.

See the input specification and sample for more details.

The objective of this game is to find a rectangular region where the total score (after multipliers) in the region is equal to the objective score. atarw wants to know how long it will take for him to find such a region. As an incompetent programmer, he has asked you to make a program that finds the number of valid rectangles given the base score ( ) and the objective score ( ). While he is playing the game, you will answer such queries.

#### Constraints

Total absolute multiplier at any point is guaranteed to be less than .                     Note: You will have to use fast input methods.

#### Input Specification

The first line will contain the four space separated integers , , , .

The next lines are of the following two forms denoting describing the multipliers:

• c x y f – an score multiplier is applied to columns .
• r x y f – an score multiplier is applied to rows .

The next lines contain two space separated integers, and , the base and objective scores respectively.

#### Output Specification lines each with a single integer corresponding to the number of rectangles that with the given base score adds up to the objective score.

#### Sample Input

3 3 3 1
c 2 3 2
c 3 3 4
r 2 3 3
3 72

#### Sample Output

2

#### Explanation for Sample Output

With a base score of 3, the grid has the following scores.

 ________________________
| \\ C||     |     |     |
|R \\ ||  1  |  2  |  3  |
|=====++=====+=====+=====|
|  1  ||  3  |  6  |  24 |
|-----++-----+-----+-----|
|  2  ||  9  |  18 |  72 |
|-----++-----+-----+-----|
|  3  ||  9  |  18 |  72 |
|_____||_____|_____|_____|

There are only two rectangular regions that have a total score of 72, the single squares and .

• commented on March 29, 2016, 11:56 p.m. edited

Any tips for speeding up my solution? Edit: https://dmoj.ca/submission/218779

• commented on March 30, 2016, 12:19 p.m. edited

Your solution seems correct. It's probably due to the speed of Java on DMOJ. The time limit for Java 7 and 8 have been increased to 4s. I tested your solution and it runs within the new time limit (just that one test case was over 3s). Congratulations!

• commented on March 30, 2016, 5:22 p.m.

Thank you :)

• commented on March 25, 2016, 3:49 p.m.

[x,y] is the multiplier only applied to columns/rows, x & y or all the ones in between.

• commented on March 25, 2016, 4:43 p.m. denotes an inclusive interval, so it is all the columns/rows from x to y, is guaranteed.

• commented on March 25, 2016, 3:36 p.m.

Do I get extra points for having the game installed?