Submission #941408

#	Time	Username	Problem	Language	Result	Execution time	Memory
941408		Error42	Aliens (IOI16_aliens)	C++17	100 / 100	147 ms	9048 KiB

aliens

#include "aliens.h"

#include <algorithm>
#include <deque>
#include <vector>

using namespace std;

using ll = long long;
using ld = long double;

struct point {
    ll l, r;
};

struct fraction {
    ll num, denom;

    bool operator <(fraction const& rhs) const {
        return num * rhs.denom < rhs.num * denom;
    }

    bool operator ==(fraction const& rhs) const {
        return num * rhs.denom == rhs.num * denom;
    }
};

struct line {
    ll m, b, k;

    ll operator() (ll const x) {
        return m * x + b;
    }

    fraction crossing(line const& rhs) const {
        // m1 * x + b1 - m2 * x - b = 0
        // (m1 - m2) * x = b2 - b1
        // x = (b2 - b1) / (m1 - m2)
        return { rhs.b - b, m - rhs.m };
    }
};

struct cht {
    deque<line> lines;

    void insert(line inserted) {
        while (lines.size() >= 2) {
            auto const crossing_a = inserted.crossing(lines[0]); 
            auto const crossing_b = lines[0].crossing(lines[1]);

            if (crossing_a < crossing_b)
                lines.pop_front();
            else if (crossing_a == crossing_b) {
                if (inserted.k >= lines[0].k)
                    lines.pop_front();
                else {
                    inserted = lines[0];
                    lines.pop_front();
                }
            }
            else
                break;
        }

        lines.push_front(inserted);
    }

    /// x must be ascending
    /// Returns: { value, k }
    pair<ll, ll> query(ll const x) {
        while (lines.size() >= 2 
            && (lines.back()(x) > lines[lines.size() - 2](x) || (lines.back()(x) == lines[lines.size() - 2](x) && lines.back().k <= lines[lines.size() - 2].k))) {
            lines.pop_back();
        }

        return { lines.back()(x), lines.back().k };
    }
};

ll sq(ll const x) {
    return x * x;
}

/// Returns: { ans, k }
pair<ll, ll> relaxed(
    ll const n,
    ll const m,
    ll const λ,
    // sorted in ascending order, subsegments left out
    vector<ll> const& l,
    vector<ll> const& r
) {
    // Let dp[i] denote the cost to cover the first i points.
    // 
    // Then dp[i] = min[k<i]( dp[k] + (r[i] - l[k + 1] + 1)^2 - max(0, r[k] - l[k + 1] + 1)^2 ) + λ =
    //            = min[k<i]( dp[k] + (r[i]+1)^2 - 2*(r[i]+1)*l[k+1] + l[k+1]^2 - max(0, r[k] - l[k + 1] + 1)^2 ) + λ =
    //            = min[k<i]( -2*l[k+1]*(r[i]+1) + dp[k] + l[k+1]^2 - max(0, r[k] - l[k + 1] + 1)^2 ) + λ + (r[i]+1)^2
    // 
    // c[k](r[i]) := -2*l[k+1]*(r[i]+1) + dp[k] + l[k+1]^2 - max(0, r[k] - l[k + 1] + 1)^2 on which we can perform CHT.
    // 
    // dp[i] = min[k<i] c[k](r[i]) + λ + (r[i]+1)^2
    // 
    // ## CHT
    // 
    // Given function f(x) = a*(x-b)^2 + c
    // f(x) = 0 <=> a*x^2 - 2*a*b*x + a*b^2 + c = 0

    vector<ll> _dp(n + 1);
    vector<ll> _k(n + 1);

    auto const dp = [&](ll const i) -> ll& {
        return _dp[i + 1];
    };

    auto const k = [&](ll const i) -> ll& {
        return _k[i + 1];
    };

    dp(-1) = 0;
    k(-1) = 0;
    cht c;
    // c[-1]
    c.insert({ -2 * l[0], dp(-1) + l[0] * l[0] + 0, k(-1) });

    for (ll i = 0; i < n; i++) {
        auto const [cost, cur_k] = c.query(r[i] + 1);

        dp(i) = cost + λ + sq(r[i] + 1);
        k(i) = cur_k + 1;

        if (i != n - 1)
            c.insert({ -2 * l[i + 1], dp(i) + sq(l[i + 1]) - sq(max(0ll, r[i] - l[i + 1] + 1)), k(i) });
    }

    return { dp(n - 1), k(n - 1) };
}

ll take_photos(
    int const n,
    int const m,
    int const k,
    // not const, for swapping
    vector<int> l1,
    vector<int> r1
) {
    vector<point> points(n);
    for (int i = 0; i < n; i++) {
        if (l1[i] > r1[i])
            swap(l1[i], r1[i]);

        points[i] = { l1[i], r1[i] };
    }

    sort(points.begin(), points.end(), [&](point const& a, point const& b) {
        return a.l < b.l || (a.l == b.l && a.r > b.r);
    });

    vector<ll> l2 = { points[0].l };
    vector<ll> r2 = { points[0].r };

    for (int i = 1; i < n; i++) {
        if (points[i].r > r2.back() || points[i].l > r2.back()) {
            l2.push_back(points[i].l);
            r2.push_back(points[i].r);
        }
    }

    ll lo = 0;
    ll hi = 2e12;

    while (lo != hi) {
        ll mid = (lo + hi) / 2;

        auto const [_cost, cur_k] = relaxed(l2.size(), m, mid, l2, r2);

        if (cur_k > k)
            lo = mid + 1;
        else
            hi = mid;
    }

    ll const λ = lo;

    auto const [cost, cur_k] = relaxed(l2.size(), m, λ, l2, r2);

    if (λ == 0)
        return cost;
    else
        return cost - cur_k * λ - (k - cur_k) * (λ - 1);
}

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 40 / 40