## Editorial for DMOPC '18 Contest 6 P5 - Quadrat Sampling

**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:

In order to maximize the raw total, each goose should fly to a cell covered by as many quadrats as possible so that it can be counted the maximum number of times. Thus, we seek where is the number of quadrats covering the cell at row and column .

For the first subtask, we can use a 2D prefix sum array to compute all in per quadrat plus post-processing. Then, for each goose, we can go over all the cells that it can reach to find the one covered by the most quadrats.

**Time complexity:**

For the second subtask, we can sweep the rows from top to bottom, keeping a data structure such as a segment tree that allows for efficient range addition updates and range maximum queries. When we reach the beginning or the end of quadrat , we add 1 to or subtract 1 from the cells from to . When we reach goose , we query the cells from to to find its .

We can then do a similar sweep from left to right to find for each goose.

**Time complexity:**

For the final subtask, we must first compress the coordinates so that the maximum row and column are . Then, we can do the same thing as in the second subtask.

**Time complexity:**

## Comments