#include "aliens.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define f first
#define se second
//#define int long long
#define pll pair<ll, ll>
#define pii pair<int, int>
using namespace std;
const int N = 3e5 + 123;
//const int N = 2e4 + 123;
const int M = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll inf = 1e16;
const ld INF = 1e17;
const ll maxR = 1e12 + 5;
struct segment {
ll l, r, l1, r1;
segment(ll l, ll r, ll l1, ll r1) : l(l), r(r), l1(l1), r1(r1) {};
};
struct line {
ll b, k;
ll cntid;
};
vector <line> lines;
ld intersect(line l1, line l2) {
return (l1.b * 1.0 - l2.b * 1.0) / (l2.k * 1.0 - l1.k * 1.0);
}
ld val(line l, ld x) {
return l.k * 1.0 * x + l.b;
}
ll vall(line l, ll x) {
return l.k * x + l.b;
}
void addline(line a) {
while (lines.size() > 1) {
ld tmp = intersect(lines[lines.size() - 1], lines[lines.size() - 2]);
if (val(lines[lines.size() - 1], tmp) > val(a, tmp))
lines.pop_back();
else
break;
}
lines.pb(a);
}
pair<ll, ll> getmin(ll x) {
ll L, R, M;
pair<ll, ll> ans = {inf, inf};
L = 0; R = lines.size() - 1;
while (L <= R) {
M = (L + R) / 2;
ans = min(ans, {vall(lines[M], x), lines[M].cntid});
if (M != lines.size() - 1)
ans = min(ans, {vall(lines[M + 1], x), lines[M + 1].cntid});
if (M != 0)
ans = min(ans, {vall(lines[M - 1], x), lines[M - 1].cntid});
if (M == lines.size() - 1) {
R = M - 1;
continue;
}
if (make_pair(vall(lines[M], x), lines[M].cntid) >= make_pair(vall(lines[M + 1], x), lines[M + 1].cntid))
L = M + 1;
else
R = M - 1;
}
return ans;
}
ll L[N], R[N], Lto[N], Rto[N], ar[N], sz = 0;
ll cntt[N];
bool isworth[N];
vector <segment> worth;
vector <ll> byl[N];
unordered_set <ll> st[M];
ll dp[N];
bool cmp(segment x, segment y) {
return x.r < y.r;
}
ll cost(ll l, ll r) {
if (l > r)
return 0;
return (r - l + 1) * (r - l + 1);
}
void add(int j) {
line tmp;
ll addd;
if (j == 1 || worth[j].l > worth[j - 1].r)
addd = 0ll;
else
addd = cost(worth[j].l, worth[j - 1].r);
tmp.b = dp[j - 1] + worth[j].l * worth[j].l - addd;
tmp.k = -2 * worth[j].l;
tmp.cntid = cntt[j - 1];
addline(tmp);
}
pll count(ll costt, int n) {
lines.clear();
dp[0] = 0;
cntt[0] = 0;
for (int i = 1; i <= n; i++) {
add(i);
pair<ld, ll> tmpp = getmin(worth[i].r + 1);
dp[i] = costt + tmpp.f + (worth[i].r + 1) * (worth[i].r + 1);
cntt[i] = tmpp.se + 1;
}
return make_pair(dp[n] - cntt[n] * costt, cntt[n]);
}
ll take_photos(int n, int m, int k, vector <int> r, vector <int> c) {
int tmp = 0;
for (int i = 0; i < n; i++) {
if (c[i] >= r[i]) {
if (st[r[i] + 1].count(c[i] + 1))
continue;
tmp++;
L[tmp] = r[i] + 1;
R[tmp] = c[i] + 1;
} else {
if (st[c[i] + 1].count(r[i] + 1))
continue;
tmp++;
L[tmp] = c[i] + 1;
R[tmp] = r[i] + 1;
}
st[L[tmp]].insert(R[tmp]);
ar[++sz] = L[tmp];
ar[++sz] = R[tmp];
}
n = tmp;
sort(ar + 1, ar + sz + 1);
ll t = unique(ar + 1, ar + sz + 1) - ar - 1;
for (int i = 1; i <= n; i++) {
Lto[i] = lower_bound(ar + 1, ar + t + 1, L[i]) - ar;
Rto[i] = lower_bound(ar + 1, ar + t + 1, R[i]) - ar;
byl[Lto[i]].pb(i);
isworth[i] = true;
}
ll curmax = 0;
for (int i = 1; i <= 2 * n; i++) {
ll localmx = 0;
for (int to : byl[i]) {
localmx = max(localmx, Rto[to]);
if (Rto[to] <= curmax)
isworth[to] = false;
}
for (int to : byl[i])
if (Rto[to] < localmx)
isworth[to] = false;
curmax = max(curmax, localmx);
}
worth.pb({-1, -1, -1, -1});
for (int i = 1; i <= n; i++) {
if (isworth[i])
worth.pb({L[i], R[i], Lto[i], Rto[i]});
}
n = worth.size() - 1;
sort(worth.begin(), worth.end(), cmp);
k = min(n, k);
ll M, L = 0, R = maxR;
ll ans;
pll val1, val2; ll p1, p2;
while (L <= R) {
// cout << L << " " << R << endl;
M = (L + R) / 2;
val1 = count(M, n);
if (val1.se < k) {
R = M - 1;
continue;
}
val2 = count(M + 1, n);
p2 = val2.se; p1 = val1.se;
if (val2.se > k) {
L = M + 1;
continue;
}
if (p1 == k) {
ans = val1.f;
break;
}
if (p2 == k) {
ans = val2.f;
break;
}
ll dif = (val1.f - val2.f) / (p1 - p2);
if ((val1.f - val2.f) % (p1 - p2) != 0)
return -1;
ans = val2.f + (k - p2) * dif;
break;
}
return ans;
}
