ABC127 F - Absolute Minima
https://atcoder.jp/contests/abc127/tasks/abc127_f
Maintain the first smallest half of a[i] and the second smallest half of a[i], call them L and R respectively. Then, the answer is sum(R)-sum(L) if L and R have the same number of elements.
To maintain them efficiently, we prepare two heaps, the one is a max-heap called L and the other is a min-heap called R. When given the input a[i] and b[i], we insert a[i] into both heaps, that is, do L.push(a[i]) and R.push(a[i]). After this operation, it might be L.top() > R.top(). If so, we swap them. After this, L.top() <= R.top() always holds. Note that L.top() <= R.top() implies L has the first smallest half of a[i] and R is also the same.
Since a[i] is counted doubly, the answer is a little different from the described above. It becomes (sum(R) - sum(L))/2. When L.top() > R.top(), two elements moves between L and R mutually. At this time, the (sum(R)-sum(L))/2 increases by x-y, where x and y are L.top() and R.top() respectively.
The following code is based on the explanation above. Clearly, we can use a balanced binary search tree or a binary indexed tree for solving this problem. BST and BIT appear in various situations. So it might be easier than the heap-based solution for experienced competitors.
By the way, as far as I know, two heap technique is written in "Cracking the Coding Interview." So it might be more well-known than many people think.
#include <iostream> #include <algorithm> #include <vector> #include <string> #include <queue> using namespace std; using ll = long long; template<class T> using minheap = priority_queue<T, vector<T>, greater<T>>; template<class T> using maxheap = priority_queue<T, vector<T>, less<T>>; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int Q; cin >> Q; maxheap<ll> L; minheap<ll> R; ll ans = 0; while (Q--) { int type; cin >> type; if (type == 1) { ll a, b; cin >> a >> b; ans += b; L.push(a); R.push(a); if (L.top() > R.top()) { ll l = L.top(); L.pop(); ll r = R.top(); R.pop(); ans += l - r; L.push(r); R.push(l); } } else { cout << L.top() << ' ' << ans << '\n'; } } }