#include "aliens.h"
#include <vector>
#include <algorithm>
#include <limits>
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
using ll = long long;
const ll INF = (ll)1e18;
std::vector<std::pair<int,int>> pts(n);
for (int i = 0; i < n; ++i)
pts[i] = { std::min(r[i], c[i]), std::max(r[i], c[i]) };
std::sort(pts.begin(), pts.end());
std::vector<ll> A(n+1), B(n+1);
for (int i = 1; i <= n; ++i) {
A[i] = pts[i-1].first;
B[i] = pts[i-1].second;
}
std::vector<ll> seg(4*(n+1), -INF);
auto build = [&](auto&& self, int idx, int L, int R)->void{
if (L == R) seg[idx] = B[L];
else {
int M = (L+R)/2;
self(self, idx*2, L, M);
self(self, idx*2+1, M+1, R);
seg[idx] = std::max(seg[idx*2], seg[idx*2+1]);
}
};
build(build, 1, 1, n);
auto query = [&](auto&& self, int idx, int L, int R, int ql, int qr)->ll {
if (qr < L || R < ql) return -INF;
if (ql <= L && R <= qr) return seg[idx];
int M = (L+R)/2;
return std::max(
self(self, idx*2, L, M, ql, qr),
self(self, idx*2+1, M+1, R, ql, qr)
);
};
std::vector<ll> dp(n+1), best(n+1);
std::vector<int> cnt(n+1), bestCnt(n+1);
ll lambda = 0;
auto solveDC = [&](auto&& self, int L, int R, int optL, int optR)->void {
if (L > R) return;
int mid = (L+R)/2;
ll bestVal = INF; int bestK=-1, bestSeg=0;
int ub = std::min(optR, mid-1);
for (int j = optL; j <= ub; ++j) {
ll mx = query(query,1,1,n,j+1,mid);
ll len = mx - A[j+1] + 1;
ll cost = len*len + lambda;
ll cand = dp[j] + cost;
int segs = cnt[j] + 1;
if (cand < bestVal || (cand==bestVal && segs<bestSeg)) {
bestVal = cand;
bestSeg = segs;
bestK = j;
}
}
best[mid] = bestVal;
bestCnt[mid] = bestSeg;
self(self, L, mid-1, optL, bestK);
self(self, mid+1,R, bestK, optR);
};
auto runWith = [&](ll lam)->std::pair<ll,int> {
lambda = lam;
std::fill(dp.begin(), dp.end(), INF);
std::fill(cnt.begin(), cnt.end(), 0);
dp[0]=0; cnt[0]=0;
solveDC(solveDC, 1, n, 0, n-1);
return { best[n], bestCnt[n] };
};
ll lo = 0, hi = 4LL*m*m + 10;
while (lo < hi) {
ll mid = (lo+hi)/2;
auto [val, used] = runWith(mid);
if (used > k) lo = mid + 1;
else hi = mid;
}
auto [finalVal, finalUsed] = runWith(lo);
return finalVal - lo * finalUsed;
}
