#include "aliens.h"
#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
typedef long long ll;
typedef std::pair<ll, ll> Line;
const ll INF = 1e18;
const int N = 1e5 + 1;
using namespace std;
int n;
vector< Line > a;
Line lines[N];
Line dp[N];
ll divide(ll a, ll b) {
int delta = 0;
if(a % b != 0)
delta = 1;
if((a > 0 && b > 0) || (a < 0 && b < 0))
return a / b + delta;
return -abs(a) / abs(b);
}
ll intersect(int a, int b) {
if(lines[a].X == lines[b].X)
return INF;
return divide(lines[a].Y - lines[b].Y, 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()) {
ll v = apply(cht[ptr - 1], x);
ll u = apply(cht[ptr], x);
if(v < u || (v == u && dp[cht[ptr - 1]].Y > dp[cht[ptr]].Y))
ptr++;
else
break;
}
return cht[ptr - 1];
}
Line check(ll lambda) {
for(int i = 0;i <= a.size();i++)
dp[i] = MP(INF * 4, INF * 4);
dp[0] = MP(0, 0);
deque< int > larger, smaller;
int larger_it = 1;
int smaller_it = 1;
for(int i = 0;i < a.size();i++) {
ll l = a[i].X, r = a[i].Y;
lines[i] = {-2 * r, 2 * r + 1 + r * r + dp[i].X};
insert(larger, larger_it, i);
while(!larger.empty()) {
int v = larger.front();
if(a[v].Y >= l)
break;
lines[v] = {-2 * a[v].X, -2 * a[v].X + 1 + a[v].X * a[v].X + dp[v].X};
insert(smaller, smaller_it, v);
larger.pop_front();
}
int pos = get(larger, larger_it, l);
if(pos != -1) {
// cerr << i + 1 << " " << pos << " " << dp[pos].Y << "d\n";
dp[i + 1] = min(dp[i + 1], MP(apply(pos, l) + l * l - 2 * l + lambda, dp[pos].Y + 1));
}
pos = get(smaller, smaller_it, r);
if(pos != -1) {
// cerr << i + 1 << " " << pos << "d\n";
dp[i + 1] = min(dp[i + 1], MP(apply(pos, r) + r * r + 2 * 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]), max(r[i], c[i])));
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);
//cerr << i.X << " " << i.Y << "\n";
}
}
a.swap(good);
}
ll tl = -INF, tr = INF, res = 0;
while(tl <= tr) {
ll m = (tl + tr) / 2;
Line mid = check(m);
//cerr << 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;
}
