MEC '16 P6 - Instruments of the Ghostwriters

View as PDF

Submit solution

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 C by R rectangular grid, where C is the number of columns and R is the number of rows. There are 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 score multipliers are equivalent to a single 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) and the objective score (O). While he is playing the game, you will answer Q such queries.

Constraints

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

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

Variable Subtask 1 [5%] Subtask 2 [5%] Subtask 3 [90%]
B -10^2 \le B \le 10^2 -10^3 \le B \le 10^3 -10^{18} \le B \le 10^{18}
O -10^9 \le O \le 10^9 -10^9 \le O \le 10^9 -10^{18} \le O \le 10^{18}
Q Q = 1 Q \le 1\,000 Q \le 100\,000
M M \le 10 M \le 100 M \le 1\,000\,000
C, R 1 \le C, R \le 5 1 \le C, R \le 20 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, R, M, Q.

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

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

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

Output Specification

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

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 (3, 2) and (3, 3).


Comments


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

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


    • 0
      aurpine  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!


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

        Thank you :)


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


    • 0
      aurpine  commented on March 25, 2016, 4:43 p.m.

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


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

    Do I get extra points for having the game installed?