VM7WC '15 #5 Gold - Tree Planting

View as PDF
Submit solution
Points: 12
Time limit: 0.3s
Memory limit: 256M
Author:
thorthugnasty
Problem type

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 (1,1). The square (x,y) would be located x-1 units to the right of (1,1) and y-1 units below (1,1). The grid is infinitely long in the positive x and y axes. The Massey Green club can perform 2 operations:

  1. Plant t (1 \le t \le 10\,000) trees at position (r,c). It is guaranteed that the Manhattan distance of square (r,c) from square (1,1) will be less than or equal to 2\,000 and that r,c are positive integers.

  2. Find the number of trees on all squares on the diagonal from squares (r,c) to (r-x,c+x). It is guaranteed that the Manhattan distance of (r,c) from square (1,1) will be less than or equal to 2\,000, 0 \le x < r, and r, c, x are positive integers.

Input Specification

The first line will contain N (1 \le N \le 400\,000), the number of commands you will be given. The next N lines each contain a command as 4 space-separated integers.

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

Output Specification

Print the sum of the answers to all the type 2 operations, modulo 10^9 + 7.

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 Output

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

123456
1X
23
324
4X
5
6

Comments


  • -1
    MstrPikachu  commented on Sept. 15, 2019, 8:08 p.m. ← edited

    oops


    • 2
      lookcook  commented on Sept. 15, 2019, 8:15 p.m. ← edit 2

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


  • 1
    TheCool1James  commented on Sept. 17, 2018, 12:33 a.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...


  • 1
    albertzhan  commented on Feb. 6, 2015, 4:05 a.m.

    Wasn't this a CCC question???