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

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)$ $(x 1, y 1)$ to $(x2, y2)$ $(x 2, y 2)$ .

Time Complexity: $\mathcal{O}(QN^2)$ $O (Q N^{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)$ $(x 1, y 1)$ to $(x2, y2)$ $(x 2, y 2)$ .

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

Comments

There are no comments at the moment.