Submission #1042118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042118		IdanRosen	Rabbit Carrot (LMIO19_triusis)	C++98	0 / 100	0 ms	348 KiB

triusis

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;

std::random_device dev;
std::mt19937 rng(dev());
std::uniform_int_distribution<std::mt19937::result_type> dist(0, SIZE_MAX); // distribution in range [0, MAX_SIZE_T_VAL)

struct treap_node_data {
    ll height;

    bool add_lz = false;
    ll add_val;
};

struct treap_node {
    /** general fields and functions in a treap */
    treap_node_data data;
    size_t prio = dist(rng);
    treap_node *left = nullptr;
    treap_node *right = nullptr;

    explicit treap_node(const treap_node_data &data) : data(data) {
    }

    template<typename It>
    static treap_node *build(It first, It last) {
        if (first == last) return nullptr;

        ll dis = last - first;
        if (dis == 1) {
            return new treap_node(*first);
        } else {
            It mid = first + dis / 2;
            treap_node *res;
            merge(&res, build(first, mid), build(mid, last));
            return res;
        }
    }

    // get the keys in the tree (copy to iterator)
    static void get_keys_in_order(treap_node *node, treap_node_data **iter) {
        if (node == nullptr) return;
        push_lazy(node);

        get_keys_in_order(node->left, iter);
        **iter = node->data;
        (*iter)++;
        get_keys_in_order(node->right, iter);
    }

    /** implicit treap (implicit search tree) */

    ll sz = 1;

    static ll get_size(treap_node *node) { return node == nullptr ? 0 : node->sz; }

    /** base functions for the treap */

    // split tree llo two subtrees:
    // first subtree holds the range [0, pos)
    // second subtree holds the range [pos, n)
    static void split_at_pos(treap_node *tree, ll pos, treap_node **left, treap_node **right) {
        if (tree == nullptr) {
            *left = *right = nullptr;
            return;
        }
        push_lazy(tree);

        if (!(pos < get_size(tree))) {
            // pos is out of the tree, nothing to split
            *left = tree;
            *right = nullptr;
            return;
        }

        ll left_sz = get_size(tree->left);
        if (left_sz < pos) {
            // the node we are looking for is in the right subtree
            *left = tree;

            treap_node *sub_left;
            split_at_pos(tree->right, pos - left_sz - 1, &sub_left, right);
            (*left)->right = sub_left;

            pull_update(*left);
        } else {
            // the node we are looking for is in the left subtree
            *right = tree;

            treap_node *sub_right;
            split_at_pos(tree->left, pos, left, &sub_right);
            (*right)->left = sub_right;

            pull_update(*right);
        }
    }

    static void merge(treap_node **root, treap_node *left, treap_node *right) {
        if (left == nullptr && right == nullptr) *root = nullptr;
        else if (left == nullptr) {
            push_lazy(right);
            *root = right;
        } else if (right == nullptr) {
            push_lazy(left);
            *root = left;
        } else {
            push_lazy(left);
            push_lazy(right);

            if (left->prio > right->prio) {
                *root = left;

                treap_node *sub_root;
                merge(&sub_root, left->right, right);
                pull_update(sub_root);
                (*root)->right = sub_root;
            } else {
                *root = right;
                treap_node *sub_root;
                merge(&sub_root, left, right->left);
                pull_update(sub_root);
                (*root)->left = sub_root;
            }

            pull_update(*root);
        }
    }

    /** other useful extension functions */

    // split tree llo three subtrees:
    // first subtree holds the range [0, pos)
    // second subtree holds the range [pos, pos + len)
    // third subtree holds the range [pos + len, n)
    static void split_by_range(treap_node *tree, ll pos, ll len,
                               treap_node **l, treap_node **m, treap_node **r) {
        split_at_pos(tree, pos, l, m);
        split_at_pos(*m, len, m, r);
    }

    static void insert_subrange(treap_node **root, treap_node *new_node, ll pos) {
        // split the root by the key of the new node
        treap_node *left;
        treap_node *right;
        split_at_pos(*root, pos, &left, &right);

        merge(&left, left, new_node); // merge the left subtree and the new node, store result in left
        merge(root, left, right); // now merge left and right, store the result in root
    }

    static void extract_subrange(treap_node **root, ll pos, ll len, treap_node **res) {
        // split the root by the key
        treap_node *left;
        treap_node *right;
        split_by_range(*root, pos, len, &left, res, &right);

        // merge the left and right subtrees back
        merge(root, left, right);
    }

    static treap_node *node_at_pos(treap_node *node, ll pos) {
        treap_node *curr = node;

        while (curr != nullptr) {
            push_lazy(curr);

            ll left_sz = get_size(curr->left);

            if (left_sz == pos) return curr;
            else if (left_sz < pos) {
                curr = curr->right;
                pos -= left_sz + 1;
            } else {
                curr = curr->left;
            }
        }

        return nullptr;
    }

    /** general functions for lazy propagation */

    static void push_lazy(treap_node *node) {
        if (node == nullptr) return;

        if (node->data.add_lz) {
            ll val = node->data.add_val;
            node->data.height += val;

            if (node->left != nullptr) {
                if (node->left->data.add_lz) node->left->data.add_val += val;
                else {
                    node->left->data.add_val = val;
                    node->left->data.add_lz = true;
                }
            }
            if (node->right != nullptr) {
                if (node->right->data.add_lz) node->right->data.add_val += val;
                else {
                    node->right->data.add_val = val;
                    node->right->data.add_lz = true;
                }
            }

            node->data.add_lz = false;
        }
    }

    static void pull_update(treap_node *node) {
        if (node == nullptr) return;
        push_lazy(node->left);
        push_lazy(node->right);
        node->sz = 1 + get_size(node->left) + get_size(node->right);
    }

    /** other */
    static void add_to_range(treap_node *node, ll val) {
        if (node == nullptr) return;
        push_lazy(node);

        node->data.add_lz = true;
        node->data.add_val = val;
    }

    static ll upper_bound(treap_node *node, ll value) {
        if (node == nullptr) return 0;

        ll index = 0;

        while (node != nullptr) {
            push_lazy(node);

            if (node->data.height <= value) {
                index += get_size(node->left) + 1;
                node = node->right;
            } else
                node = node->left;
        }

        return index;
    }

};

using treap = treap_node;

struct limit_t {
    bool has_low_bound;
    ll max_low_diff;

    bool has_high_bound;
    ll max_high_diff;
};

ll min_cost(const vector<ll> &arr, const vector<limit_t> &limits) {

    treap *left_dp = nullptr;
    treap *right_dp = nullptr;

    ll cost = 0;

    for (ll i = 0; i < arr.size(); i++) {
        ll val = arr[i];
        limit_t lim = limits[i];

        if (!lim.has_low_bound && !lim.has_high_bound) {
            if (right_dp != nullptr) {
                delete right_dp;
                right_dp = nullptr;
            }
            if (left_dp != nullptr) {
                delete left_dp;
                left_dp = nullptr;
            }
        } else if (!lim.has_low_bound) {
            if (right_dp != nullptr) {
                delete right_dp;
                right_dp = nullptr;
            }

            treap::add_to_range(left_dp, -lim.max_high_diff);

            ll in = treap::upper_bound(left_dp, val);
            if (in == treap::get_size(left_dp)) {
                treap::insert_subrange(&left_dp, new treap(treap_node_data{val, false}), treap::get_size(left_dp));
                treap::insert_subrange(&right_dp, new treap(treap_node_data{val, false}), 0);
            } else {
                treap::insert_subrange(&left_dp, new treap(treap_node_data{val, false}), in);
                treap::insert_subrange(&left_dp, new treap(treap_node_data{val, false}), in);

                treap *tmp;
                treap::split_at_pos(left_dp, treap::get_size(left_dp) - 1, &left_dp, &tmp);
                cost += tmp->data.height - val;
                delete tmp;
            }
        } else if (!lim.has_high_bound) {
            if (left_dp != nullptr) {
                delete left_dp;
                left_dp = nullptr;
            }

            treap::add_to_range(right_dp, lim.max_low_diff);

            ll in = treap::upper_bound(right_dp, val);
            if (in == 0) {
                treap::insert_subrange(&right_dp, new treap(treap_node_data{val, false}), 0);
                treap::insert_subrange(&left_dp, new treap(treap_node_data{val, false}), 0);
            } else {
                treap::insert_subrange(&right_dp, new treap(treap_node_data{val, false}), in);
                treap::insert_subrange(&right_dp, new treap(treap_node_data{val, false}), in);

                treap *tmp;
                treap::split_at_pos(right_dp, 1, &tmp, &right_dp);
                cost += val - tmp->data.height;
                delete tmp;
            }
        } else {
            treap::add_to_range(left_dp, -lim.max_high_diff);
            treap::add_to_range(right_dp, lim.max_low_diff);

            if (left_dp != nullptr &&
                val < treap::node_at_pos(left_dp, treap::get_size(left_dp) - 1)->data.height) {
                ll in = treap::upper_bound(left_dp, val);
                treap::insert_subrange(&left_dp, new treap(treap_node_data{val, false}), in);
                treap::insert_subrange(&left_dp, new treap(treap_node_data{val, false}), in);

                treap *tmp;
                treap::split_at_pos(left_dp, treap::get_size(left_dp) - 1, &left_dp, &tmp);
                cost += tmp->data.height - val;

                treap::insert_subrange(&right_dp, tmp, 0);
            } else if (right_dp != nullptr && treap::node_at_pos(right_dp, 0)->data.height < val) {
                ll in = treap::upper_bound(right_dp, val);
                treap::insert_subrange(&right_dp, new treap(treap_node_data{val, false}), in);
                treap::insert_subrange(&right_dp, new treap(treap_node_data{val, false}), in);

                treap *tmp;
                treap::split_at_pos(right_dp, 1, &tmp, &right_dp);
                cost += val - tmp->data.height;

                treap::insert_subrange(&left_dp, tmp, treap::get_size(left_dp));
            } else {
                treap::insert_subrange(&left_dp, new treap(treap_node_data{val, false}),
                                       treap::get_size(left_dp) - 1);
                treap::insert_subrange(&right_dp, new treap(treap_node_data{val, false}), 0);
            }
        }
    }

    return cost;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll n, m;
    cin >> n >> m;

    vector<ll> arr(n);
    for (auto &i: arr) cin >> i;
    reverse(arr.begin(), arr.end());
    arr.push_back(0);

    vector<limit_t> lims(n);
    for (int i = 0; i < n; i++) lims[i] = {false, 0, true, m};
    lims.push_back({false, 0, true, m});

    treap *left_dp = nullptr;
    treap *right_dp = nullptr;

    ll cost = 0;

    for (ll i = 0; i < arr.size(); i++) {
        ll val = arr[i];
        limit_t lim = lims[i];

        if (right_dp != nullptr) {
            delete right_dp;
            right_dp = nullptr;
        }

        treap::add_to_range(left_dp, -lim.max_high_diff);

        ll in = treap::upper_bound(left_dp, val);
        if (in == treap::get_size(left_dp)) {
            treap::insert_subrange(&left_dp, new treap(treap_node_data{val, false}), treap::get_size(left_dp));
            treap::insert_subrange(&right_dp, new treap(treap_node_data{val, false}), 0);
        } else {
            treap::insert_subrange(&left_dp, new treap(treap_node_data{val, false}), in);
            treap::insert_subrange(&left_dp, new treap(treap_node_data{val, false}), in);

            treap *tmp;
            treap::split_at_pos(left_dp, treap::get_size(left_dp) - 1, &left_dp, &tmp);
            ++cost;
//            cost += tmp->data.height - val;
            delete tmp;
        }
    }

    for (int i = treap::get_size(left_dp) - 1; i >= 0; i--) {
        auto node = treap::node_at_pos(left_dp, i);

        if (0 < node->data.height) ++cost;
        else break;
    }

    cout << cost;

}

Compilation message (stderr)

triusis.cpp: In function 'll min_cost(const std::vector<long long int>&, const std::vector<limit_t>&)':
triusis.cpp:266:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  266 |     for (ll i = 0; i < arr.size(); i++) {
      |                    ~~^~~~~~~~~~~~
triusis.cpp: In function 'int main()':
triusis.cpp:379:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  379 |     for (ll i = 0; i < arr.size(); i++) {
      |                    ~~^~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37