#include <bits/stdc++.h>
#include "cross.h"
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pll;
struct segtree{
ll T[606060];
void insert(ll p, ll s, ll e, ll v)
{
T[p] ++;
if(s == e) return;
else if(v <= (s + e >> 1)){
insert(p << 1, s, s + e >> 1, v);
}
else{
insert(p << 1 | 1, (s + e >> 1) + 1, e, v);
}
}
ll getval(ll p, ll s, ll e, ll k)
{
if(s == e) return s;
else if(k > T[p << 1 | 1]){
return getval(p << 1, s, s + e >> 1, k - T[p << 1 | 1]);
}
else{
return getval(p << 1 | 1, (s + e >> 1) + 1, e, k);
}
}
};
segtree T;
vector <pll> P;
vector <ll> X;
ll n, ans;
ll SelectCross(int k, vector<int> I, vector <int> O)
{
ll i, x, y;
n = I.size();
for(i=0; i<n; i++){
P.emplace_back(I[i], O[i]);
X.push_back(O[i]);
}
sort(P.begin(), P.end(), [&](pll &pa, pll &pb){
if(pa.first == pb.first) return pa.second < pb.second;
else return pa.first > pb.first;
});
sort(X.begin(), X.end());
X.erase(unique(X.begin(), X.end()), X.end());
for(i=0; i<k-1; i++){
x = lower_bound(X.begin(), X.end(), P[i].second) - X.begin();
T.insert(1, 0, n - 1, x);
}
for(; i<n; i++){
if(k > 1){
y = T.getval(1, 0, n - 1, k - 1);
y = X[y];
}
else y = 1e9;
x = P[i].first; y = min(y, P[i].second);
ans = max(ans, 2 * x * y - x * x);
x = lower_bound(X.begin(), X.end(), P[i].second) - X.begin();
T.insert(1, 0, n - 1, x);
}
return ans;
}
