oj.uz

Submission #1025537

# Submission time Handle Problem Language Result Execution time Memory
1025537 2024-07-17T06:32:35 Z caterpillow Safety (NOI18_safety) C++17
100 / 100
 701 ms 21152 KB 
#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

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

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 464 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 472 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 13944 KB Output is correct
2 Correct 656 ms 19796 KB Output is correct
3 Correct 688 ms 20524 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 464 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 472 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 456 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 464 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 472 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 456 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 464 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 472 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 456 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 11 ms 860 KB Output is correct
29 Correct 9 ms 864 KB Output is correct
30 Correct 7 ms 860 KB Output is correct
31 Correct 4 ms 796 KB Output is correct
32 Correct 7 ms 660 KB Output is correct
33 Correct 5 ms 852 KB Output is correct
34 Correct 6 ms 856 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 464 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 472 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 456 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 11 ms 860 KB Output is correct
35 Correct 9 ms 864 KB Output is correct
36 Correct 7 ms 860 KB Output is correct
37 Correct 4 ms 796 KB Output is correct
38 Correct 7 ms 660 KB Output is correct
39 Correct 5 ms 852 KB Output is correct
40 Correct 6 ms 856 KB Output is correct
41 Correct 10 ms 860 KB Output is correct
42 Correct 8 ms 684 KB Output is correct
43 Correct 5 ms 860 KB Output is correct
44 Correct 6 ms 860 KB Output is correct
45 Correct 8 ms 740 KB Output is correct
46 Correct 5 ms 860 KB Output is correct

Subtask #9
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 464 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 472 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 433 ms 13944 KB Output is correct
20 Correct 656 ms 19796 KB Output is correct
21 Correct 688 ms 20524 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 456 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 11 ms 860 KB Output is correct
38 Correct 9 ms 864 KB Output is correct
39 Correct 7 ms 860 KB Output is correct
40 Correct 4 ms 796 KB Output is correct
41 Correct 7 ms 660 KB Output is correct
42 Correct 5 ms 852 KB Output is correct
43 Correct 6 ms 856 KB Output is correct
44 Correct 10 ms 860 KB Output is correct
45 Correct 8 ms 684 KB Output is correct
46 Correct 5 ms 860 KB Output is correct
47 Correct 6 ms 860 KB Output is correct
48 Correct 8 ms 740 KB Output is correct
49 Correct 5 ms 860 KB Output is correct
50 Correct 701 ms 21152 KB Output is correct
51 Correct 569 ms 17488 KB Output is correct
52 Correct 228 ms 16720 KB Output is correct
53 Correct 250 ms 19524 KB Output is correct
54 Correct 294 ms 20048 KB Output is correct
55 Correct 263 ms 16992 KB Output is correct
56 Correct 401 ms 18680 KB Output is correct
57 Correct 207 ms 17232 KB Output is correct
58 Correct 178 ms 14492 KB Output is correct
59 Correct 280 ms 19024 KB Output is correct