#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " " << x << endl
#define _ << " " <<
using llint = long long;
const int MAXN = 5e4 + 5;
const llint INF = 1e17;
vector<pair<int, int>> I, P;
struct Event {
int x, type, id;
Event() {}
Event(int x, int type, int id) : x(x), type(type), id(id) {}
friend bool operator<(const Event &A, const Event &B) {
if (A.x == B.x) return A.type < B.type;
return A.x < B.x;
}
};
vector<pair<int, int>> get_intervals(int n, const vector<int> &r,
const vector<int> &c) {
vector<Event> e;
for (int i = 0; i < n; ++i) {
int lo = min(r[i], c[i]);
int hi = max(r[i], c[i]);
e.emplace_back(lo, 0, i);
e.emplace_back(hi, 1, i);
}
sort(e.begin(), e.end());
multiset<int> ms;
vector<pair<int, int>> ret;
for (const auto &p : e) {
if (p.type == 0) {
ms.insert(p.x);
continue;
}
int lo = min(r[p.id], c[p.id]);
ms.erase(ms.find(lo));
if (ms.empty() || *ms.begin() > lo) ret.emplace_back(lo, p.x);
}
return ret;
}
// y = ax + b = cx + d
// x(a - c) == d - b
double intersect(pair<llint, llint> &A, pair<llint, llint> &B) {
return (double) (B.second - A.second) / (A.first - B.first);
}
void replace(stack<pair<llint, llint>> &src, stack<pair<llint, llint>> &dest) {
while (!src.empty()) {
if (dest.size() < 3) {
dest.push(src.top());
src.pop();
continue;
}
pair<llint, llint> A, B, C;
while (dest.size() >= 3) {
B = dest.top(); dest.pop();
A = dest.top();
C = src.top();
if (intersect(A, C) < intersect(B, C))
continue;
dest.push(B);
break;
}
dest.push(C);
src.pop();
}
}
llint take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
for (int i = 0; i < n; ++i) P.emplace_back(r[i], c[i]);
I = get_intervals(n, r, c);
n = (int)I.size();
I.emplace_back(1e9, 1e9);
vector<llint> dp_prev(n, 0), dp_curr(n, 0);
stack<pair<llint, llint>> env_prev, env_curr;
for (int i = 0; i < n; ++i) {
dp_prev[i] =
(llint)(I[i].second - I[0].first + 1) * (I[i].second - I[0].first + 1);
llint A = -2LL * (I[i + 1].first - 1);
llint B = dp_prev[i] + (llint)(I[i + 1].first - 1) * (I[i + 1].first - 1) -
(llint)max(0, I[i].second - I[i + 1].first + 1) *
max(0, I[i].second - I[i + 1].first + 1);
env_curr.push({A, B});
}
replace(env_curr, env_prev);
for (int i = 1; i < k; ++i) {
int t = 0;
for (int j = 0; j < n; ++j) {
llint c = (llint) I[j].second * I[j].second;
llint x = (llint) I[j].second;
llint env_a = -INF, env_b = -INF;
dp_curr[j] = INF;
while (!env_prev.empty() && t < j) {
auto p = env_prev.top();
if (c + p.first * x + p.second <= dp_curr[j]) {
dp_curr[j] = c + p.first * x + p.second;
env_a = p.first; env_b = p.second;
env_prev.pop();
++t;
continue;
}
break;
}
if (env_a != -INF || env_b != -INF) {
env_prev.push({env_a, env_b});
--t;
}
dp_curr[j] = min(dp_curr[j], dp_prev[j]);
llint A = -2LL * (I[j + 1].first - 1);
llint B = dp_curr[j] +
(llint)(I[j + 1].first - 1) * (I[j + 1].first - 1) -
(llint)max(0, I[j].second - I[j + 1].first + 1) *
max(0, I[j].second - I[j + 1].first + 1);
env_curr.push({A, B});
}
swap(dp_prev, dp_curr);
while (!env_prev.empty()) env_prev.pop();
replace(env_curr, env_prev);
}
return dp_prev[n - 1];
}
