## VM7WC '15 #5 Gold - Tree Planting

View as PDF

Points: 12
Time limit: 0.3s
Memory limit: 256M

Author:
Problem type
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

The Massey Green club has gone out into the field to plant trees (for bonus marks, of course). The field is a grid with the top-left square labelled . The square would be located units to the right of and units below . The grid is infinitely long in the positive and axes. The Massey Green club can perform 2 operations:

Plant trees at position . It is guaranteed that the Manhattan distance of square from square will be less than or equal to and that are positive integers.

Find the number of trees on all squares on the diagonal from squares to . It is guaranteed that the Manhattan distance of from square will be less than or equal to , , and are positive integers.

#### Input Specification

The first line will contain , the number of commands you will be given. The next lines each contain a command as space-separated integers.

The first integer will be either or , for the type of operation you will be asked to perform. If the type is , the next integers are in that order. If the type is , the next 3 integers are in that order.

#### Output Specification

Print the sum of the answers to all the type operations, modulo .

#### Sample Input

5
1 2 3 2
2 4 1 3
1 4 3 4
1 3 2 3
2 4 1 3

#### Sample Output

7

#### Explanation for Sample Input

The first command places 2 trees at the spot . The second command asks you to count the trees between and , as marked by the "X"s on the grid. The 2 trees from the first command fall in this area, therefore the answer is . For the last command, the trees from the first and the third commands fall in the range, therefore the result is . You should print .

• commented on Sept. 15, 2019, 4:08 p.m. edited

oops

• commented on Sept. 15, 2019, 4:15 p.m. edited

Print the sum of the answers to all the type 2 operations, modulo 10^9+7. (so 2 + 5 = 7)

• commented on Sept. 16, 2018, 8:33 p.m.

I noticed something odd, as I increased my 2D array size, I got more and more cases correct until I hit approx sqrt((256 mb -> bits)/64) as my 2D array...

• commented on Feb. 5, 2015, 11:05 p.m.

Wasn't this a CCC question???

• commented on July 23, 2017, 3:13 p.m.

You may be thinking of Nutrient Tree.

• commented on Feb. 5, 2015, 11:22 p.m.

Not that I know of.