#include "bits/stdc++.h"
#include "aliens.h"

using ll = long long;
using namespace std;

struct convex_hull_trick {
    static constexpr ll INF = 1e15;

    struct Line {
        ll k = 0, b = 0;

        Line() = default;
        Line(ll k, ll b) : k(k), b(b) {}

        ll get(ll x) const {
            return k * x + b;
        }
    };

    vector<pair<Line, int>> container;

    convex_hull_trick() = default;

    void add(ll k, ll b) {
        Line A(k, b);
        
        while (!container.empty()) {
            auto [B, k] = container.back();
            
            ll x = (B.b - A.b) / (A.k - B.k);

            if (x <= k) {
                container.pop_back();
            } else {
                container.emplace_back(A, x);
                break;
            }
        }

        if (container.empty()) {
            container.emplace_back(A, -INF);
        }
    }

    ll get(ll x) const {
        auto it = prev(upper_bound(container.begin(), container.end(), x, [](ll x, auto A) {
            return A.second <= x;
        }));
        return it->first.get(x);
    }
};

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    vector<pair<int, int>> A;

    for (int i = 0; i < n; i++) {
        A.emplace_back(min(r[i], c[i]), max(r[i], c[i]));
    }

    sort(A.begin(), A.end(), [](auto A, auto B) -> bool {
        return A.first < B.first || (A.first == B.first && A.second > B.second);
    });

    vector<pair<int, int>> B;

    int mx = -1;

    for (auto [l, r] : A) {
        if (mx < r) {
            B.emplace_back(l, r + 1);
            mx = r;
        }
    }

    convex_hull_trick cht;

    cht.add(-2 * B[0].first, 1ll * B[0].first * B[0].first);

    ll val;

    for (int i = 0; i < (int)B.size(); i++) {
        val = cht.get(B[i].second) + 1ll * B[i].second * B[i].second;
        
        if (i + 1 < (int)B.size()) {
            ll s = max(0, B[i].second - B[i + 1].first);
            s *= s;

            cht.add(-2 * B[i + 1].first, val - s + 1ll * B[i + 1].first * B[i + 1].first);
        }
    }

    return val;
}
#include "bits/stdc++.h"
#include "aliens.h"

using ll = long long;
using namespace std;

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    vector<pair<int, int>> A;

    for (int i = 0; i < n; i++) {
        A.emplace_back(min(r[i], c[i]), max(r[i], c[i]));
    }

    sort(A.begin(), A.end(), [](auto A, auto B) -> bool {
        return A.first < B.first || (A.first == B.first && A.second > B.second);
    });

    vector<pair<int, int>> B;

    int mx = -1;

    for (auto [l, r] : A) {
        if (mx < r) {
            B.emplace_back(l, r);
            mx = r;
        }
    }

    auto square = [](auto P) -> ll {
        ll x = P.second - P.first + 1;
        if (x < 0) {
            return 0;
        }
        return x * x;
    };

    auto inter = [](auto P1, auto P2) -> pair<int, int> {
        return make_pair(max(P1.first, P2.first), min(P1.second, P2.second));
    };

    auto merge = [](auto P1, auto P2) -> pair<int, int> {
        return make_pair(min(P1.first, P2.first), max(P1.second, P2.second));
    };

    while (B.size() > k) {
        ll mn = INT32_MAX;
        int b = -1;

        for (int i = 1; i < (int)B.size(); i++) {
            ll s = square(merge(B[i], B[i - 1])) - square(B[i]) - square(B[i - 1]) + square(inter(B[i], B[i - 1]));
            if (mn > s) {
                b = i;
                mn = s;
            }
        }

        B[b - 1].second = B[b].second;
        B.erase(B.begin() + b);
    }

    ll cur = square(B[0]);

    for (int i = 1; i < (int)B.size(); i++) {
        cur += square(B[i]) - square(inter(B[i], B[i - 1]));
    }

    return cur;
}

answer.code:101:4: error: redefinition of ‘ll take_photos(int, int, int, std::vector<int>, std::vector<int>)’
  101 | ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
      |    ^~~~~~~~~~~
answer.code:54:4: note: ‘ll take_photos(int, int, int, std::vector<int>, std::vector<int>)’ previously defined here
   54 | ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
      |    ^~~~~~~~~~~