제출 #1042118

#제출 시각아이디문제언어결과실행 시간메모리
1042118IdanRosenRabbit Carrot (LMIO19_triusis)C++98
0 / 100
0 ms348 KiB
#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; }

컴파일 시 표준 에러 (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++) {
      |                    ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...