Comments
On BledDest → Codeforces Round 995 (Div. 3), 23 months ago
0

Consider that the profit can only change at prices $$$a_i$$$ or $$$b_i$$$. You can visualize profit as a step function with steps at $$$a_i$$$ and $$$b_i$$$. Therefore we need only check these "boundary" prices. Moreover, we can efficiently calculate profit for a given price using binary search over sorted $$$a_i$$$ and $$$b_i$$$. The sorted $$$b_i$$$ will tell us the number of buyers for some price. The sorted $$$a_i$$$ will tell us the number of buyers leaving a positive review for some price. The difference between buyers and positive review buyers tells us the number of negative review buyers. We need only take the maximum profit over these boundary prices, discounting prices giving us excessive negative reviews. This results in $$$O(n*lg(n))$$$, which passes.