//based off of koosaga...why does he do it DOUBLE?
#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5 + 10;
const int MAXM = 1e6 + 10;
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))
ll sqr (ll x) {
return x * x;
}
template<class T>
void setmin (T &a, T b) {
if (b < a) {
a = b;
}
}
template<class T>
void setmax (T &a, T b) {
if (a < b) {
a = b;
}
}
int N, M, K;
int mxy[MAXM];
ll X[MAXN], Y[MAXN];
//line:
struct line {
ll m, b;
int id;
line (ll _m, ll _b, int _id) : m(_m), b(_b), id(_id) {}
ll val (ll x) const {
return m * x + b;
}
#warning Is using fraction really enough? Or will it possibly
pll intersect (const line &a) const {
//careful, might have to change to double
pll p(b - a.b, a.m - m);
if (p.se < 0) {
p.fi *= -1;
p.se *= -1;
}
return p;
}
};
int compare (pll p1, pll p2) {
//p1.fi * p2.se, p1.se * p2.fi
#warning do we need int128 here to compare? int128 might not even be supported in some places
ll ltval = p1.fi * p2.se, rtval = p1.se * p2.fi;
if (ltval < rtval) {
return -1;
} else if (ltval == rtval) {
return 0;
} else {
return 1;
}
}
struct convex {
vector<line> hull;
int ptr;
ll x;
convex() : hull(), ptr(), x(LLONG_MIN) {}
void clear() {
hull.clear();
ptr = 0;
x = LLONG_MIN;
}
void insert (line t) {
if (hull.empty()) {
hull.push_back(t);
return;
}
line bk = hull.back();
assert(bk.m <= t.m);
if (bk.m == t.m && t.b <= bk.b) {
return;
}
bool curerase = false;
while (hull.size() >= 2) {
int hsiz = hull.size();
line l2 = hull[hsiz - 2];
pll ph = l2.intersect(hull.back()), pt = l2.intersect(t);
if (compare(pt, ph) <= 0) {
if (hsiz == ptr + 1) {
curerase = true;
}
hull.pop_back();
} else {
break;
}
}
if (curerase) {
ptr = int(hull.size()) - 1;
}
hull.push_back(t);
}
line query (ll t) {
assert(t >= x);
for (; ptr + 1 < hull.size(); ptr++) {
if (hull[ptr].val(t) > hull[ptr + 1].val(t)) {
break;
}
}
x = t;
return hull[ptr];
}
} cht;
ll dp[MAXN];
int use[MAXN];
void moo (ll cost) {
cht.clear();
dp[0] = 0;
use[0] = 0;
for (int i = 1; i <= N; i++) {
cht.insert(line(4 * X[i], -(2 * sqr(X[i]) + dp[i - 1]), i - 1));
line lq = cht.query(Y[i]);
dp[i] = 2 * sqr(Y[i]) - lq.val(Y[i]) + cost;
if (i != N) {
dp[i] -= 2 * sqr(max(0ll, Y[i] - X[i + 1]));
}
use[i] = use[lq.id] + 1;
}
}
ll take_photos (int nnn, int mmm, int kkk, vector<int> rrr, vector<int> ccc) {
N = nnn;
M = mmm;
K = kkk;
//R, C
fillchar(mxy, -1);
for (int i = 0; i < N; i++) {
int x = rrr[i], y = ccc[i];
if (x > y) {
swap(x, y);
}
setmax(mxy[x], y);
}
N = 0;
for (int x = 0; x < M; x++) {
int y = mxy[x];
if (y == -1) {
continue;
}
if (N == 0 || Y[N] < y) {
N++;
X[N] = x - 1; //better for the algebra.
Y[N] = y;
}
}
setmin(K, N); //IMPORTANT!!! Note: N is adjusted. Therefore, it may not be true that K <= N -- need to do it again.
ll lo = 0, hi = 2e12;
while (hi - lo > 1) {
ll mid = (lo + hi) / 2;
moo(2 * mid + 1);
if (use[N] <= K) {
hi = mid;
} else {
lo = mid;
}
}
moo(2 * hi);
//debug("hi = %lld. use[N] = %d\n", hi, use[N]);
return dp[N] / 2 - hi * K;
}
