We first must determine what is meant by a "guaranteed win". From the description, we are guaranteed to win at a certain time if there is no possible way for the opponent to win, regardless of what happens in the future. Therefore, we consider the worst case scenario: we fail to get any points on unsolved problems after the time, and our opponent immediately perfectly solves any problems that they haven't solved.

Suppose we are checking if we win at time ~t~. Then, we sum up the points for both ourselves and our opponent. Then, we suppose that we earn 0 more points, and the opponent gets perfect on every problem they have remaining. That is, our opponent receives ~P~ plus whatever time bonus is earned by submitting at time ~t~ for each problem they have yet to submit to. If our score is still higher, then we are guaranteed to win at time ~t~. We can find the minimal ~t~ by performing a binary search.

For the first two subtasks, it suffices to perform a binary search per query and loop through all submissions to determine the points the two teams can get.

Time Complexity: ~\mathcal{O}(QN \log N)~

For the third subtask, we can optimize our summation process by using a data structure such as a Binary Indexed Tree. However, we cannot simply have the indexes of our BIT represent time, since it can be up to ~10^{10}~. Therefore, we must compress all possible times that appear, which can be done by processing all of the queries first. Be wary that your count of how many problems the other team has solved by a given time ~t~ is correct; another BIT may be needed to accomplish this.

Also be careful that a submission that scores ~0~ does not get any time bonus.

Time Complexity: ~\mathcal{O}(Q \log^2 N)~