Submission #1246736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246736		idk_anything_i_guess	Safety (NOI18_safety)	C++20	0 / 100	23 ms	8812 KiB

safety

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// Function to set up fast I/O
void setup_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
}

// Solves the L1 Isotonic Regression problem for a non-decreasing sequence using PAVA.
// It finds the optimal block partitions using L2 PAVA (mean-based), which is O(N),
// and then calculates the medians for each block to get the L1 solution.
std::vector<long long> compute_isotonic_nondecreasing(const std::vector<long long>& y) {
    int n = y.size();
    if (n == 0) {
        return {};
    }

    // Active set for PAVA, stores pairs of (mean, weight) for each pool.
    std::vector<std::pair<double, int>> pools;

    for (long long val : y) {
        pools.push_back({(double)val, 1});
        // Merge pools as long as the non-decreasing property is violated.
        while (pools.size() > 1 && pools.back().first < pools[pools.size() - 2].first) {
            auto p2 = pools.back();
            pools.pop_back();
            auto p1 = pools.back();
            pools.pop_back();

            double merged_mean = (p1.first * p1.second + p2.first * p2.second) / (p1.second + p2.second);
            int merged_weight = p1.second + p2.second;
            pools.push_back({merged_mean, merged_weight});
        }
    }

    // Reconstruct the final solution vector from the pools.
    std::vector<long long> result(n);
    int current_idx = 0;
    for (const auto& pool : pools) {
        int weight = pool.second;
        // Create a temporary vector for the elements in the current block.
        std::vector<long long> block_elements;
        block_elements.reserve(weight);
        for (int i = 0; i < weight; ++i) {
            block_elements.push_back(y[current_idx + i]);
        }
        
        // Find the median of the block for the L1 solution.
        std::nth_element(block_elements.begin(), block_elements.begin() + (weight - 1) / 2, block_elements.end());
        long long median = block_elements[(weight - 1) / 2];

        // Assign the median to all elements in this block.
        for (int i = 0; i < weight; ++i) {
            result[current_idx + i] = median;
        }
        current_idx += weight;
    }

    return result;
}

void solve() {
    int n;
    long long h;
    std::cin >> n >> h;

    std::vector<long long> s(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> s[i];
    }

    // --- 1. Upper Bound Problem ---
    // Transform S -> A such that we need a non-decreasing U'.
    std::vector<long long> A(n);
    for (int i = 0; i < n; ++i) {
        A[i] = s[i] + (long long)i * h;
    }
    // Solve for the optimal non-decreasing U'.
    std::vector<long long> U_prime = compute_isotonic_nondecreasing(A);
    // Transform back to get the upper bound U on S'.
    std::vector<long long> U(n);
    for (int i = 0; i < n; ++i) {
        U[i] = U_prime[i] - (long long)i * h;
    }

    // --- 2. Lower Bound Problem ---
    // Transform S -> B such that we need a non-increasing L'.
    std::vector<long long> B(n);
    for (int i = 0; i < n; ++i) {
        B[i] = s[i] - (long long)i * h;
    }
    // To find non-increasing L', solve for non-decreasing on -B and negate the result.
    std::vector<long long> minus_B(n);
    for (int i = 0; i < n; ++i) {
        minus_B[i] = -B[i];
    }
    std::vector<long long> L_prime_neg = compute_isotonic_nondecreasing(minus_B);
    // Transform back to get the lower bound L on S'.
    std::vector<long long> L(n);
    for (int i = 0; i < n; ++i) {
        L[i] = -L_prime_neg[i] + (long long)i * h;
    }

    // --- 3. Calculate Final Cost ---
    // The optimal S'[i] is the projection of S[i] onto the interval [L[i], U[i]].
    long long total_cost = 0;
    for (int i = 0; i < n; ++i) {
        long long s_final_i = s[i];
        if (s_final_i < L[i]) {
            s_final_i = L[i];
        }
        if (s_final_i > U[i]) {
            s_final_i = U[i];
        }
        total_cost += std::abs(s[i] - s_final_i);
    }

    std::cout << total_cost << std::endl;
}

int main() {
    setup_io();
    solve();
    return 0;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 4
• Subtask 3: 0 / 9
• Subtask 4: 0 / 5
• Subtask 5: 0 / 6
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 22
• Subtask 9: 0 / 29