ABC312_C – Invisible Hand

問題
提出
1. 解けた

問題

C - Invisible Hand

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

提出

Submission #44834618 - UNIQUE VISION Programming Contest 2023 Summer(AtCoder Beginner Contest 312)

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

解けた

りんごの値段が0の時、売り手の人数は0人、買い手の人数はM人になる。
$x円の時の売り手の人数-買い手の人数をf(x)$とすると$f(0)=-M$である。
$A_i,B_i$のうち最小の値段をTとすると、$f(T)=-M+1$になる(売る人が増えるか買う人が減るか)。
$A_i,B_i$を経るたび、f(T)は増加していく。
よって、二分探索が使える。
二分探索の計算量は$O(log(max(A_{max},B_{max})))$となる。
左端と右端の中央が条件を満たすか否か計算するとき、あらかじめソートした$A_i,B_i$を使えば、それぞれ$O(log(A_i))$と$O(log(B_i))$の計算量になる。

全体として計算量は$O(N\log(N)+O((\log(A_i)+\log(B_i))\log(\max(A_{max},B_{max}))))$になる。
一番大きい計算量は$O(N\log(N))$で、$N=210^5$なので間に合う。