Submission #231161

#	Time	Username	Problem	Language	Result	Execution time	Memory
231161		DedMaxim	Aliens (IOI16_aliens)	C++17	4 / 100	6 ms	384 KiB

aliens

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

using namespace std;

using ll = long long;

namespace NSolver {

template <typename TLookupType>
void ImplementSMAWK(TLookupType lookup,
        const std::vector<size_t>& rows,
        const std::vector<size_t>& columns,
        std::vector<size_t>& result) {
    if (rows.empty()) {
        return;
    }

    /// REDUCE
    std::vector<size_t> survivingColumns;
    for (size_t column: columns) {
        while (true) {
            if (survivingColumns.empty()) {
                break;
            }
            size_t row = rows[survivingColumns.size() - 1];

            const auto& firstValue = lookup(row, column);
            const auto& secondValue = lookup(row, survivingColumns.back());

            if (!firstValue.has_value() || (secondValue.has_value() && *firstValue >= *secondValue)) {
                break;
            }
            survivingColumns.pop_back();
        }
        if (survivingColumns.size() < rows.size()) {
            survivingColumns.push_back(column);
        }
    }

    std::vector<size_t> oddRows;
    for (size_t i = 1; i < rows.size(); i += 2) {
        oddRows.push_back(rows[i]);
    }
    ImplementSMAWK(lookup, oddRows, columns, result);


    std::unordered_map<size_t, size_t> columnIndices;
    for (size_t i = 0; i != survivingColumns.size(); ++i) {
        columnIndices[survivingColumns[i]] = i;
    }


    /// INTERPOLATE
    size_t start = 0;
    for (size_t r = 0; r < rows.size(); r += 2) {
        size_t row = rows[r];
        size_t stop = survivingColumns.size() - 1;
        size_t argmin = survivingColumns[start];
        auto minimum = lookup(row, argmin);

        if (r + 1 < rows.size()) {
            stop = columnIndices[result[rows[r + 1]]];
        }

        for (size_t column = start + 1; column <= stop; ++column) {
            auto val = lookup(row, survivingColumns[column]);
            if (column == start || (val.has_value() && (!minimum.has_value() || *val < *minimum))) {
                argmin = survivingColumns[column];
                minimum = val.value();
            }
        }

        result[row] = argmin;
        start = stop;
    }
}

template<typename TLookupType>
std::vector<size_t> SMAWK(int n, int m, TLookupType lookup, bool transpose = false) {
    std::vector<size_t> rows(n);
    std::vector<size_t> columns(m);

    std::iota(rows.begin(), rows.end(), 0);
    std::iota(columns.begin(), columns.end(), 0);

    if (transpose) {
        std::swap(rows, columns);
    }

    std::vector<size_t> result(rows.size());

    auto lookupTranspose = [&](size_t i, size_t j) {
        return transpose ? lookup(j, i) : lookup(i, j);
    };
    ImplementSMAWK(lookupTranspose, rows, columns, result);
    return result;
}

const long long  INF = 1ll << 35;
using ll = long long;

template <typename TPenaltyFunct, typename TConvertFunction, typename T = ll>
std::vector<std::pair<size_t, T>> Solve(size_t n, TPenaltyFunct penalty, T init, TConvertFunction convert) {
    size_t r = 0;

    std::vector<std::pair<size_t, std::optional<T>>> N(n + 1); // 1 indexation
    std::vector<std::pair<size_t, std::optional<T>>> E(n + 1), D(n + 1);

    D[0] = {0, init};
    E[0] = {0, convert(init)};

    auto B = [&](size_t i, size_t j) {
        if (!D[i].second.has_value()) {
            D[i] = {E[i].first, convert(E[i].second.value())};
        }
        return D[i].second.value() + penalty(i, j);
    };

    for (size_t c = 1; c <= n;) {
        assert(r < c);
        size_t p = std::min(2 * c - r, n);

        size_t gRows = c - r + 1;
        size_t gCols = p - c + 1;

        auto GLookup = [&](int i, int j) {
            if (i == 0) return N[c + j].second;
            else return std::optional<T>(B(r - 1 + i, c + j));
        };
        auto GLookupIndex = [&](int i, int j) {
            if (i == 0) return N[c + i].first;
            else return size_t(r - 1 + i);
        };

        const std::vector<size_t> F = SMAWK(gRows, gCols, GLookup, true);

        E[c] = std::make_pair(GLookupIndex(F[0], 0), GLookup(F[0], 0));
        D[c] = std::make_pair(E[c].first, convert(E[c].second));

        size_t j = c + 1;
        for (; j <= p; ++j) {
            T val = B(j - 1, j);

            if (val < GLookup(F[j - c], j - c)) {
                E[j] = std::make_pair(j - 1, std::optional<T>(val));
                D[j] = std::make_pair(E[j].first, convert(E[j].second));
                break;
            } else {
                E[j] = std::make_pair(GLookupIndex(F[j - c], j - c), GLookup(F[j - c], j - c));
                D[j] = std::make_pair(E[j].first, convert(E[j].second));
                if (B(j - 1, p) < GLookup(F[p - c], p - c)) {
                    for (size_t tmp = j + 1; tmp <= p; ++tmp) {
                        N[tmp] = std::make_pair(GLookupIndex(F[tmp - c], tmp - c), GLookup(F[tmp - c], tmp - c));
                    }
                    break;
                }
            }
        }

        if (j <= p) {
            c = j + 1;
            r = j - 1;
        } else {
            r = std::max(r, r - 1 + F[p - c]);
            c = p + 1;
        }
    }

    std::vector<std::pair<size_t, T>> result(n + 1);
    for (size_t i = 0; i <= n; ++i) {
        result[i] = {E[i].first, E[i].second.value()};
    }
    return result;
}

}


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;
    }

    ll sqr(ll a, bool check = false) {
        return check ? sqr(std::max(a, 0ll)) : a * a;
    }

    std::pair<size_t, ll> check(ll lambda) {
        auto penalty = [&](int i, int j) {
            return lambda +
                sqr(r[j] - l[i + 1]) -
                sqr(r[i] - l[i + 1], true);
        };

        auto convert = [&](std::optional<long long> x) {
            return x;
        };
        auto result = NSolver::Solve(n, penalty, 0ll, convert);
        /*std::cerr << "lambda v2 = " << lambda << std::endl;
        for (int i = 0; i <= n; ++i) {
            std::cerr << result[i].second << ' ';
        }
        std::cerr << std::endl;*/
        return result[n];
    }

    ll solve() {
        process();

        ll l = 0;
        ll r = 1e13;

        while(l < r) {
            ll mid = ((l + r) >> 1);
            if (check(mid).first < k) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return check(r).second - r * 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();
}

Compilation message (stderr)

aliens.cpp: In function 'll Solver::solve()':
aliens.cpp:238:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (check(mid).first < k) {
                 ~~~~~~~~~~~~~~~~~^~~

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