Submission #228078

#	Time	Username	Problem	Language	Result	Execution time	Memory
228078		DedMaxim	Aliens (IOI16_aliens)	C++17	100 / 100	191 ms	5912 KiB

aliens

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

using namespace std;

using ll = long long;


struct TConvexHullTrick {
    struct TLine {
        ll a;
        ll b;
        int id;

        TLine(ll a = 0, ll b = 0, int id = 0)
            : a(a), b(b), id(id) {
        }
    };

    std::deque<TLine> Lines;
 
    TConvexHullTrick() {
        Lines.clear();
    }
 
    bool bad(const TLine& l1, const TLine& l2, const TLine& l3) {
        return (l1.b - l3.b) * (l2.a - l1.a) < (l1.b - l2.b) * (l3.a - l1.a);
    }

    void add(ll a, ll b, int id) {
        TLine line(a, b, id);
        while (Lines.size() >= 2
                && bad(Lines[Lines.size() - 2], Lines[Lines.size() - 1], line)) {
            Lines.pop_back();
        }
        Lines.push_back(line);
    }

    ll func(const TLine &d, ll x) {
        return d.a * x + d.b;
    }

    std::pair<ll, int> get(ll x) {
        while (Lines.size() >= 2 && func(Lines[0], x) > func(Lines[1], x)) {
            Lines.pop_front();
        }
        return std::make_pair(func(Lines[0], x), Lines[0].id);
    }
};


namespace Solver {
    const int N = 1e5 + 5;
    std::pair<int, int> input[N];
    int l[N], r[N];
    int n, m, k;

    ll dp[N];
    int trace[N];
 
    void process() {
        std::sort(input, input + n, [](const auto& x, const auto& y) {
            return x.first < y.first || (x.first == y.first && x.second > y.second);
        });

        int rmax = -1;
        int cnt = 0;
        for (int i = 0; i != n; ++i) {
            if (rmax < input[i].second) {
                rmax = input[i].second;
                ++cnt;
                l[cnt] = input[i].first;
                r[cnt] = input[i].second;
            }
        }
        n = cnt;
    }

    int check(ll lambda) {
        TConvexHullTrick cht;

        memset(dp, 0, sizeof dp);
        memset(trace, 0, sizeof trace);

        auto sqr = [](int i, int j, bool checkZero) {
            if (!checkZero || r[j] >= l[i]) {
                return (r[j] - l[i]) * 1ll *(r[j] - l[i]);
            } else {
                return 0ll;
            }
        };

        cht.add(-2 * l[1], 1LL * l[1] * l[1], 0);
        for (int i = 1; i <= n; ++i) {
            pair<ll, int> g = cht.get(r[i]);

            dp[i] = g.first + 1LL * r[i] * r[i] + lambda;
            trace[i] = g.second;

            ll bCoef = dp[i] - sqr(i + 1, i, true) + 1ll * l[i + 1] * l[i + 1];
            cht.add(-2 * l[i + 1], bCoef, i);
        }

        int pos = n, cnt = 0;
        while(pos) {
            ++cnt;
            pos = trace[pos];
        }
        return cnt;
    }

    ll solve() {
        process();

        ll l = 0, r = 1e13;
        while(l < r) {
            ll mid = ((l + r) >> 1);
            if (check(mid) <= k) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        check(l); // l = lambda_opt
        return dp[n] - l * k;
    }
};
 
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    Solver::n = n;
    Solver::m = m;
    Solver::k = k;
    for (int i = 0; i < n; ++i) {
        if (r[i] > c[i]) {
            std::swap(r[i], c[i]);
        }

        Solver::input[i].first = r[i];
        Solver::input[i].second = ++c[i];
    }

    return Solver::solve();
}

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