#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
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 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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
