Editorial for Back to School '24 P2 - Cheating - Olympiads Online Judge

Editorial for Back to School '24 P2 - Cheating

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

Subtask 1:

We can put all $N$ $N$ students in a queue starting with $0$ $0$ points. For each question $i$ $i$ , we add $A_i$ $A_{i}$ to the score of the first $B_i$ $B_{i}$ students, and move the $B_i$ $B_{i}$ students to the end of the queue.

Time Complexity: $O(MN)$ $O (M N)$

Subtask 2:

We can further optimize our solution from subtask 1 by noticing that it is not required to iterate through the queue's values individually to add score. We can store the index of the first student in the queue as index $f$ $f$ , which is originally $0$ $0$ . We can then notice that for each question $i$ $i$ , we will increase the score of the students in the range of $f$ $f$ to $f + B_i$ $f + B_{i}$ (where this range may wrap from end to start), and the new $f$ $f$ would be $f + B_i + 1$ $f + B_{i} + 1$ . We can further optimize this increase by using a difference array to answer the queries.

Time Complexity: $O(N + M)$ $O (N + M)$

Comments

There are no comments at the moment.