## IOI '22 P3 - Radio Towers

View as PDF

Points: 30 (partial)
Time limit: 2.0s
Memory limit: 1G

Problem type
Allowed languages
C++

There are radio towers in Jakarta. The towers are located along a straight line and numbered from to from left to right. For each such that , the height of tower is metres. The heights of the towers are distinct.

For some positive interference value , a pair of towers and (where ) can communicate with each other if and only if there is an intermediary tower , such that

• tower is to the left of tower and tower is to the right of tower , that is, , and
• the heights of tower and tower are both at most metres.

Pak Dengklek wants to lease some radio towers for his new radio network. Your task is to answer questions of Pak Dengklek which are of the following form: given parameters , and ( and ), what is the maximum number of towers Pak Dengklek can lease, assuming that

• Pak Dengklek can only lease towers with indices between and (inclusive), and
• the interference value is , and
• any pair of radio towers that Pak Dengklek leases must be able to communicate with each other.

Note that two leased towers may communicate using an intermediary tower , regardless of whether tower is leased or not.

#### Implementation Details

You should implement the following procedures:

void init(int N, std::vector<int> H)

• : the number of radio towers.
• : an array of length describing the tower heights.
• This procedure is called exactly once, before any calls to max_towers.
int max_towers(int L, int R, int D)

• , : the boundaries of a range of towers.
• : the value of .
• This procedure should return the maximum number of radio towers Pak Dengklek can lease for his new radio network if he is only allowed to lease towers between tower and tower (inclusive) and the value of is .
• This procedure is called exactly times.

#### Example

Consider the following sequence of calls:

init(7, [10, 20, 60, 40, 50, 30, 70])

max_towers(1, 5, 10)


Pak Dengklek can lease towers , , and . The example is illustrated in the following picture, where shaded trapezoids represent leased towers.

Towers and can communicate using tower as an intermediary, since and . Towers and can communicate using tower as an intermediary. Towers and can communicate using tower as an intermediary. There is no way to lease more than towers, therefore the procedure should return .

max_towers(2, 2, 100)


There is only tower in the range, thus Pak Dengklek can only lease tower. Therefore the procedure should return .

max_towers(0, 6, 17)


Pak Dengklek can lease towers and . Towers and can communicate using tower as an intermediary, since and . There is no way to lease more than towers, therefore the procedure should return .

#### Constraints

• (for each such that )
• (for each and such that )

1. (4 points) There exists a tower such that
• for each such that : , and
• for each such that : .
2. (11 points) ,
3. (12 points)
4. (14 points)
5. (17 points) ,
6. (19 points) The value of is the same across all max_towers calls.
7. (23 points) No additional constraints.

• line :
• line :
• line : for question

• line : the return value of max_towers for question