Editorial for Another Random Contest 1 P2 - Two Sequences

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

Subtask 1

For every query, enumerate from $L$ ~L~ to $R$ ~R~ and determine the value for every position using prefix sum.

Time Complexity: $\mathcal O(NQ)$ ~\mathcal O(NQ)~

Subtask 2

Let's call $U = A_L + A_{L+1} + \dots + A_{K-1} + A_K$ and $V = B_{K+1} + B_{K+2} + \dots + B_{R-1} + B_R$ .

Since all numbers in $A$ ~A~ and $B$ ~B~ are positive, $U$ ~U~ will always increase and $V$ ~V~ will always decrease as $K$ ~K~ moves to the right. One can interpret two expressions as increasing and decreasing functions. It is clear that the minimum will occur when the two functions intersect. Binary search can be used to find the intersection or points closest to the intersection. If $U > V$ ~U > V~, binary search right, and if $V > U$ ~V > U~, binary search left.

Time Complexity: $\mathcal O(N + Q \log N)$ ~\mathcal O(N + Q \log N)~

Comments

There are no comments at the moment.