Editorial for SAC '22 Code Challenge 2 P2 - Cookie Sprinkler

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: maxcruickshanks

Intended Solution

Maintain a 2D integer array.

For each type $1$ ~1~ query, add $1$ ~1~ to the specified cell.

For each type $2$ ~2~ query, run a nested for-loop to accumulate all the cookies in the rectangle bounded by $(x1, y1)$ ~(x1, y1)~ to $(x2, y2)$ ~(x2, y2)~.

Time Complexity: $\mathcal{O}(QN^2)$ ~\mathcal{O}(QN^2)~

Alternative Solution

Maintain a list of cookies that you have added.

For each type $1$ ~1~ query, add a cookie to that list.

For each type $2$ ~2~ query, loop through that list and sum up all the cookies that are in the rectangle bounded by $(x1, y1)$ ~(x1, y1)~ to $(x2, y2)$ ~(x2, y2)~.

Time Complexity: $\mathcal{O}(Q^2)$ ~\mathcal{O}(Q^2)~

Comments

There are no comments at the moment.