## Editorial for An Animal Contest 1 P6 - Alpaca Distancing

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

#### Subtask 1

This subtask was intended to reward brute force solutions.

**Time Complexity:**

#### Subtask 2

Let represent the maximum number of friends that William can keep among the first alpacas. Sort the alpacas by position. Brute forcing the transition suffices, using to update if the alpacas at positions and are outside each other's ranges.

**Time Complexity:**

#### Subtask 3

There are many approaches hereafter. A binary indexed tree (BIT) for prefix maximum queries will be used in this solution.

To optimize the transition, we add the values of all alpacas that are outside the range of the alpaca into the BIT. Since the positions of alpacas are in increasing order, all alpacas after the are also outside the range of alpacas in the BIT. The last step is to satisfy the range requirement of the alpaca, which we do by querying the BIT for the maximum value in the range from to .

**Time Complexity:**

#### Subtask 4

For full marks, coordinate compression of the values used in the BIT is required.

**Time Complexity:**

## Comments