#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;
ll n, m, k, lef[M], xs[N], ans[M];
struct Node {
ll l, r;
ll a, b;
} node[M << 2];
struct Change {
ll id;
ll a, b;
};
vector <Change> changes[N];
ll eval(ll a, ll b, ll x) {
return 1ll * a * xs[x] + b;
}
void update(ll id, ll a, ll b, vector <Change> &changes) {
ll q = node[id].l + node[id].r >> 1;
ll 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(ll id, ll x) {
ll f = eval(node[id].a, node[id].b, x);
if (node[id].l == node[id].r) {
return f;
}
ll 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(ll 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;
}
ll 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 (ll 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) {
ll i = xs[j];
if (j && i == xs[j - 1]) {
continue;
}
while (!st.empty() && st.top().yy > lef[i]) {
rollback(st.top().xx);
st.pop();
}
ll p = st.empty()? 0: xs[st.top().xx];
ll l = lef[i];
update(0, -2 * (l - 1), (l - 1) * (l - 1) + ans[p] - max(0ll, p - l + 1) * max(0ll, p - l + 1), changes[j]);
st.push({j, lef[i]});
res = ans[i] = lambda + i * i + query(0, j);
}
return res - k * lambda;
}
ll ternary_search(ll l, ll r) {
if (r <= l + 1) {
return max(calc(l), calc(r));
}
ll q = l + r >> 1;
if (calc(q) > calc(q + 1)) {
return ternary_search(l, q);
} else {
return ternary_search(q + 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 (ll i = 1; i <= m; ++i) {
lef[i] = i + 1;
}
for (ll i = 0; i < n; ++i) {
r[i]++, c[i]++;
ll x = max(r[i], c[i]);
ll 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;
}
