SAC '22 Code Challenge 2 P2 - Cookie Sprinkler

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 256M

Problem type

To help build a new home for Mr. DeMello Santa, you were tasked with maintaining a 2D, N \times N tank of milk in his house.

In this tank, you will be asked to perform Q queries of 2 types:

1 x y: Add one new cookie to the tank of milk at position (x, y).

2 x1 y1 x2 y2: Add sprinkles to all the cookies once in the rectangle from (x1, y1) to (x2, y2).

Can you help Santa determine the sum of the sprinkles placed on the cookies?

Input Specification

The first line will contain N (1 \le N \le 500) and Q (1 \le Q \le 500), the square size of the milk tank and the number of queries.

The next Q lines will contain one of the queries listed above.

For type 1 queries, they will contain x (1 \le x \le N) and y (1 \le y \le N), the coordinates of the new cookie.

For type 2 queries, they will contain x1, y1, x2, and y2 (1 \le x1 \le x2 \le N, 1 \le y1 \le y2 \le N), a rectangle where all cookies are given one more sprinkle.

Note: One cell can contain multiple cookies.

Output Specification

Output the sum of the sprinkles placed on the cookies.

Sample Input

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

Sample Output


Explanation for Sample Output

In all the queries, the cookie at (2, 3) is sprinkled 3 times, the cookie at (5, 6) is sprinkled 2 times, and the cookie at (4, 4) is sprinkled 2 times.


There are no comments at the moment.