Submission #1025537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025537		caterpillow	Safety (NOI18_safety)	C++17	100 / 100	701 ms	21152 KiB

safety

#include <bits/stdc++.h>
#include <random>

using namespace std;

using db = long double;
using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<typename Tuple, size_t... Is>
void print_tuple(const Tuple& t, index_sequence<Is...>) {
    ((cerr << (Is == 0 ? "{" : ", ") << get<Is>(t)), ...);
    cerr << "}";
}

template<typename... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
    print_tuple(t, index_sequence_for<Args...>{});
    return os;
}

ostream& operator<<(ostream& os, string& s) {
    for (char c : s) os << c; 
    return os;
}

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
    os << "{"; 
    int g = size(o); 
    for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
    os << "}";
    return os;
}

template<typename T, typename V>
ostream& operator<<(ostream& os, const pair<T, V> p) {
    os << "{" << p.f << ", " << p.s << "}";
    return os;
}

template <typename T, typename... V>
void printer(const char *names, T &&head, V &&...tail) {
    int i = 0;
    while (names[i] != '\0' && names[i] != ',') i++;
    constexpr bool is_str = is_same_v<decay_t<T>, const char*>;
    if constexpr (is_str) cerr << head; // ignore directly passed strings
    else cerr.write(names, i) << " = " << head; 
    if constexpr (sizeof...(tail)) cerr << (is_str ? "" : ","), printer(names + i + 1, tail...);
    else cerr << endl;
}

#ifdef LOCAL
#define dbg(...) std::cerr << __LINE__ << ": ", printer(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

/*

let dp[i][j] to be the min cost of making the i'th tower height j
dp[i][j] = min (j - h <= k <= j + h) dp[i - 1][k] + abs(s[i] - j)

assume the function is convex
then, the min part of the transition is just splitting the function apart at its midpoint and then moving the two halves
left and right by h, keeping it convex
abs(s[i] - j) is also a convex function, meaning convex will stay convex

the function begins as convex, and hence each dp column will always be convex

maintain set of slope changing points as a treap

*/

random_device rd;
mt19937 mt(rd());

using ptr = struct Node*;
struct Node {
    ptr l, r;
    int pri, sz;
    ll k, lazy;

    Node(ll k) : k(k) {
        pri = mt();
        sz = 1;
        l = r = 0;
        lazy = 0;
    }
};

void operator+=(pl& lhs, pl rhs) {
    lhs.f += rhs.f;
    lhs.s += rhs.s;
}

int sz(ptr n) { return n ? n->sz : 0; }

void push(ptr n) {
    if (!n) return;
    n->k += n->lazy;
    if (n->l) n->l->lazy += n->lazy;
    if (n->r) n->r->lazy += n->lazy;
    n->lazy = 0;
}

ptr pull(ptr n) {
    if (!n) return 0;
    push(n->l), push(n->r);
    n->sz = sz(n->l) + 1 + sz(n->r);
    return n;
}

pair<ptr, ptr> split(ptr n, ll k) {
    if (!n) return {0, 0};
    push(n);
    if (k <= n->k) {
        auto [l, r] = split(n->l, k);
        n->l = r;
        return {l, pull(n)};
    } else {
        auto [l, r] = split(n->r, k);
        n->r = l;
        return {pull(n), r};
    }
}

pair<ptr, ptr> spliti(ptr n, int i) {
    if (!n) return {0, 0};
    push(n);
    if (i <= sz(n->l)) {
        auto [l, r] = spliti(n->l, i);
        n->l = r;
        return {l, pull(n)};
    } else {
        auto [l, r] = spliti(n->r, i - 1 - sz(n->l));
        n->r = l;
        return {pull(n), r};
    }
}

ptr merge(ptr l, ptr r) {
    if (!l || !r) return max(l, r);
    push(l), push(r);
    ptr t;
    if (l->pri > r->pri) l->r = merge(l->r, r), t = l;
    else r->l = merge(l, r->l), t = r;
    return pull(t);
}

void ins(ptr& n, ll k) {
    auto [l, r] = split(n, k);
    n = merge(l, merge(new Node(k), r));
}

void tour(ptr n, int p = 1) {
    if (p) cerr << "tour: ";
    if (n) {
        push(n);
        tour(n->l, 0);
        cerr << n->k << " ";
        tour(n->r, 0);
    }
    if (p) cerr << endl;
}

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    ll n, k; cin >> n >> k;
    ptr tree = 0;
    pl func = {0, 0};
    F0R (_, n) {
        ll h; cin >> h;

        // spread at min
        auto [l, r] = spliti(tree, sz(tree) - func.f);
        if (l) l->lazy -= k;
        if (r) r->lazy += k;
        tree = merge(l, r);
        func.s -= k * func.f;

        // ditch negative dp values
        tie(l, r) = split(tree, 0);
        tree = r;

        // insert function
        F0R (i, 2) ins(tree, h);

        // update turning points
        func += {1, -h};
    }
    while (func.f > 0) {
        auto [l, r] = spliti(tree, sz(tree) - 1);
        tree = l;
        ll x = r->k;
        ll y = func.f * x + func.s;
        func.f--;
        func.s = y - x * func.f;
    }
    cout << func.s << endl;
}

Compilation message (stderr)

safety.cpp:181:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  181 | main() {
      | ^~~~

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