#include "aliens.h"
#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ld double
typedef long long ll;
typedef std::pair<ll, ll> Line;
const ll INF = 1e17;
const int N = 1e5 + 1;
using namespace std;
int n;
vector< Line > a;
Line lines[N];
Line dp[N];
ld intersect(int a, int b) {
if(lines[a].X == lines[b].X)
return INF;
return (lines[a].Y - lines[b].Y) * 1.0 / (lines[b].X - lines[a].X);
}
ll apply(int a, ll x) {
return lines[a].X * x + lines[a].Y;
}
void insert(deque<int> &cht, int& ptr, int i) {
while(1) {
if(cht.empty()) {
cht.push_back(i);
break;
}
int v = cht.end()[-1];
if(intersect(v, i) == INF) {
if(lines[v].Y <= lines[i].Y)
break;
cht.pop_back();
if(!cht.empty())
continue;
}
else {
if(cht.size() > 1) {
int u = cht.end()[-2];
if(intersect(v, i) < intersect(u, v)) {
cht.pop_back();
continue;
}
}
}
cht.push_back(i);
break;
}
ptr = min(ptr, (int)cht.size());
}
int get(const deque< int > &cht, int &ptr, ll x) {
if(cht.empty())
return -1;
while(ptr < cht.size()) {
if(intersect(cht[ptr - 1], cht[ptr]) <= x)
ptr++;
else
break;
}
return cht[ptr - 1];
}
Line check(ll lambda) {
for(int i = 0;i <= a.size();i++)
dp[i] = MP(4e18, 4e18);
dp[0] = MP(0, 0);
deque< int > larger;
int larger_it = 1;
for(int i = 0;i < a.size();i++) {
ll l = a[i].X, r = a[i].Y;
lines[i] = {-2 * (l - 1), (l - 1) * (l - 1) + dp[i].X};
if(i && a[i - 1].Y >= a[i].X) {
lines[i].Y -= (a[i - 1].Y - a[i].X + 1) * (a[i - 1].Y - a[i].X + 1);
}
insert(larger, larger_it, i);
int pos = get(larger, larger_it, r);
assert(pos != -1);
dp[i + 1] = {apply(pos, r) + r * r + lambda, dp[pos].Y + 1};
}
return dp[a.size()];
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
{
set<int> st;
vector< Line > good;
for(int i = 0;i < n;i++)
a.push_back(MP(min(r[i], c[i]) + 1, max(r[i], c[i]) + 1));
sort(a.begin(), a.end(),
[](pair<int, int> l, pair<int, int> r) {
if(l.X != r.X)
return l.X < r.X;
return l.Y > r.Y;
}
);
for(pair<int, int> i: a) {
while(!st.empty() && *st.begin() < i.X)
st.erase(st.begin());
if(st.empty() || *st.rbegin() < i.Y) {
st.insert(i.Y);
good.push_back(i);
}
}
a.swap(good);
}
k = min(k, (int)a.size());
ll tl = -INF, tr = INF, res = -INF - 1;
while(tl <= tr) {
ll m = (tl + tr) / 2;
Line mid = check(m);
//cerr << mid.X << " " << mid.Y << " " << tl << " " << tr << "\n";
if(mid.Y >= k) {
tl = m + 1;
res = m;
}
else {
tr = m - 1;
}
}
Line mid = check(res);
ll answer = mid.X - k * res;
return answer;
}
