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(MN)~

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.