Editorial for DMOPC '19 Contest 2 P3 - Selection

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

For subtask 1, a simple brute force algorithm will suffice. For each query, we can sort the subarray, take the th best item, and then revert the array to its original state.

Time complexity:

For subtask 2, we can build a Binary Indexed Tree (BIT) over our array and update it accordingly. For each query, we use our BIT to find the number of 1s in our subarray. If this is more than , then the th best item has goodness 1. Otherwise, it has goodness 0.

Time complexity:

For subtask 3, we instead build a BIT for the number of elements for each possible . Similar to subtask , we can use our BIT's to find for each possible , the number of elements that have as its goodness. The th best item is thus the highest possible such that the number of elements with a value greater than or equal to is more than , which can be checked with our BITs.

Time complexity:

• commented on March 21, 2020, 11:24 p.m. edit 2

For the third subtask, how do the queries process the range l, r? It seems like the BIT does not track the range.

edit: figured it out, ignore pls

• commented on Oct. 21, 2019, 11:46 a.m. edit 2

A segment tree for number frequency would suffice as well. O(20mlog(n))

• commented on Oct. 21, 2019, 1:41 p.m.

"26 pbds" - ChrisT