This problem can be solved using sparse table and segment tree.

Let's assume, there is student A who can start from point 5 and end at any point between points 5 and 16. Also there is student B who can run from 10 to 20. There is student C who can run from 7 to 30.

Now if you have to pick student A, whom will you pick next? student B or C?
The answer is C. Because this student can go furthest.

Now, for determining who will start after whom, you need to build a segment tree, where you can query that, which student can start in the range of A (5 - 16) and go furthest.

Now, if you pick your first student, you can tell who starts in second, then third and so on, until the finishing line is crossed. And of course you will pick someone to start first, who starts from the starting line of the race, and can run furthest.
This way, you can calculate the number of students for 1 race in O(n log n) complexity.

But the problem requires better complexity. You can build a sparse tree, from which you can tell, if you start with student A, what is the maximum end point you can achieve by picking 2x2^{x} students. You can build the first column of that table from previous segment tree.

Now, you can solve 1 race in O(log n) complexity.

Statistics

64% Solution Ratio
Um_nikEarliest, Jun '21
user.233155Fastest, 0.0s
Deshi_TouristLightest, 21 MB
user.233155Shortest, 1701B
Toph uses cookies. By continuing you agree to our Cookie Policy.