MEC '16 P6 - Instruments of the Ghostwriters - Olympiads Online Judge

MEC '16 P6 - Instruments of the Ghostwriters

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.4s

Java 8 1.8s

Memory limit: 256M

Author:

aurpine

Problem types

atarw is playing an excellently-crafted video game made by aurpine and Hypnova. This game takes place on a $C$ ~C~ by $R$ ~R~ rectangular grid, where $C$ ~C~ is the number of columns and $R$ ~R~ is the number of rows. There are $M$ ~M~ 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 $4\times$ ~4\times~ score multipliers are equivalent to a single $16\times$ ~16\times~ 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 ( $B$ ~B~) and the objective score ( $O$ ~O~). While he is playing the game, you will answer $Q$ ~Q~ such queries.

Constraints

Total absolute multiplier at any point is guaranteed to be less than $10^9$ ~10^9~.

$f \in \mathbb{Z}, -7 \le f \le 7$ ~f \in \mathbb{Z}, -7 \le f \le 7~

Variable	Subtask 1 [5%]	Subtask 2 [5%]	Subtask 3 [90%]
$B$ ~B~	$-10^2 \le B \le 10^2$ ~-10^2 \le B \le 10^2~	$-10^3 \le B \le 10^3$ ~-10^3 \le B \le 10^3~	$-10^{18} \le B \le 10^{18}$ ~-10^{18} \le B \le 10^{18}~
$O$ ~O~	$-10^9 \le O \le 10^9$ ~-10^9 \le O \le 10^9~	$-10^9 \le O \le 10^9$ ~-10^9 \le O \le 10^9~	$-10^{18} \le O \le 10^{18}$ ~-10^{18} \le O \le 10^{18}~
$Q$ ~Q~	$Q = 1$ ~Q = 1~	$Q \le 1\,000$ ~Q \le 1\,000~	$Q \le 100\,000$ ~Q \le 100\,000~
$M$ ~M~	$M \le 10$ ~M \le 10~	$M \le 100$ ~M \le 100~	$M \le 1\,000\,000$ ~M \le 1\,000\,000~
$C, R$ ~C, R~	$1 \le C, R \le 5$ ~1 \le C, R \le 5~	$1 \le C, R \le 20$ ~1 \le C, R \le 20~	$1 \le C, R \le 40$ ~1 \le C, R \le 40~

Note: You will have to use fast input methods.

Input Specification

The first line will contain the four space separated integers $C$ ~C~, $R$ ~R~, $M$ ~M~, $Q$ ~Q~.

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

c x y f – an $f$ ~f~ score multiplier is applied to columns $[x, y]$ ~[x, y]~.
r x y f – an $f$ ~f~ score multiplier is applied to rows $[x, y]$ ~[x, y]~.

The next $Q$ ~Q~ lines contain two space separated integers, $B$ ~B~ and $O$ ~O~, the base and objective scores respectively.

Output Specification

$Q$ ~Q~ 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

Sample Output

Explanation for Sample Output

With a base score of $3$ ~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$ ~72~, the single squares $(3, 2)$ ~(3, 2)~ and $(3, 3)$ ~(3, 3)~.

Comments

1

Zander commented on March 30, 2016, 3:56 a.m. ← edited →

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

-1

aurpine commented on March 30, 2016, 4: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!

1

Zander commented on March 30, 2016, 9:22 p.m.

Thank you :)

0

jason_zhang commented on March 25, 2016, 7:49 p.m.

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

-1

aurpine commented on March 25, 2016, 8:43 p.m. ← edited →

$[x, y]$ ~[x, y]~ denotes an inclusive interval, so it is all the columns/rows from $x$ ~x~ to $y$ ~y~, $x \le y$ ~x \le y~ is guaranteed.

6

jason_zhang commented on March 25, 2016, 7:36 p.m.

Do I get extra points for having the game installed?