#include "aliens.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define xx first
#define yy second
#define l(x) (x << 1) + 1
#define r(x) (x << 1) + 2
using namespace std;
typedef long long ll;
const ll N = 1e5 + 1;
const ll M = 1e6 + 1;
const ll inf = 1ll << 60;
int n, m, k, lef[M], xs[N];
ll ans[M];
struct Node {
int l, r;
int a;
ll b;
} node[N << 2];
struct Change {
int id;
int a;
ll b;
};
vector <Change> changes[N];
ll eval(ll a, ll b, int x) {
return 1ll * a * xs[x] + b;
}
void update(int id, int a, ll b, vector <Change> &changes) {
int q = node[id].l + node[id].r >> 1;
int l = node[id].l;
if (eval(node[id].a, node[id].b, q) > eval(a, b, q)) {
swap(node[id].a, a);
swap(node[id].b, b);
changes.push_back({id, a, b});
}
if (node[id].l == node[id].r) {
return;
}
if (eval(node[id].a, node[id].b, l) > eval(a, b, l)) {
update(l(id), a, b, changes);
} else {
update(r(id), a, b, changes);
}
}
ll query(int id, ll x) {
ll f = eval(node[id].a, node[id].b, x);
if (node[id].l == node[id].r) {
return f;
}
int q = node[id].l + node[id].r >> 1;
if (x <= q) {
return min(f, query(l(id), x));
} else {
return min(f, query(r(id), x));
}
}
void build(int id, ll l, ll r) {
node[id].l = l;
node[id].r = r;
node[id].a = 0;
node[id].b = inf;
if (l == r) {
return;
}
int q = node[id].l + node[id].r >> 1;
build(l(id), l, q);
build(r(id), q + 1, r);
}
ll calc(ll lambda) {
stack <pair <ll, ll>> st;
for (int i = 0; i < n; ++i) {
changes[i].clear();
}
fill(ans, ans + M, 0);
build(0, 0, n - 1);
auto rollback = [&](ll i) {
for (auto [id, a, b]: changes[i]) {
node[id].a = a;
node[id].b = b;
}
};
ll res = 0;
for (int j = 0; j < n; ++j) {
int i = xs[j];
if (j && i == xs[j - 1]) {
continue;
}
while (!st.empty() && st.top().yy > lef[i]) {
rollback(st.top().xx);
st.pop();
}
int p = st.empty()? 0: xs[st.top().xx];
int l = lef[i];
update(0, -2 * (l - 1), 1ll * (l - 1) * (l - 1) + ans[p] - 1ll * max(0, p - l + 1) * max(0, p - l + 1), changes[j]);
st.push({j, lef[i]});
res = ans[i] = lambda + 1ll * i * i + query(0, j);
}
return res - k * lambda;
}
ll ternary_search(ll l, ll r) {
if (l == r) {
return calc(l);
}
ll d = (r - l) / 3;
ll a = l + d;
ll b = r - d;
if (calc(a) > calc(b)) {
return ternary_search(l, b - 1);
} else {
return ternary_search(a + 1, r);
}
}
ll take_photos(int n_, int m_, int k_, std::vector<int> r, std::vector<int> c) {
n = n_, m = m_, k = k_;
for (int i = 1; i <= m; ++i) {
lef[i] = i + 1;
}
for (int i = 0; i < n; ++i) {
r[i]++, c[i]++;
int x = max(r[i], c[i]);
int y = min(r[i], c[i]);
lef[x] = min(lef[x], y);
xs[i] = x;
}
sort(xs, xs + n);
ll res = ternary_search(0, 1ll * m * m);
return res;
}
