#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 7.5e5 + 10;
int n, q;
ll h[maxn];
/// Cartesian tree data
int left_child[maxn], right_child[maxn];
int left_border[maxn], right_border[maxn];
int root, depth[maxn];
void cartesian_tree()
{
stack < int > lf;
for (int i = 1; i <= n; i ++)
{
left_child[i] = -1;
while(!lf.empty() && h[lf.top()] <= h[i])
{
left_child[i] = lf.top();
lf.pop();
}
if (lf.empty())
left_border[i] = 1;
else
left_border[i] = lf.top() + 1;
lf.push(i);
}
stack < int > rf;
for (int i = n; i >= 1; i --)
{
right_child[i] = -1;
while(!rf.empty() && h[rf.top()] < h[i])
{
right_child[i] = rf.top();
rf.pop();
}
if (rf.empty())
right_border[i] = n;
else
right_border[i] = rf.top() - 1;
rf.push(i);
}
for (int i = 1; i <= n; i ++)
{
if (left_border[i] == 1 && right_border[i] == n)
{
root = i;
break;
}
}
}
void calc_depth(int ver)
{
//cout << "vertex " << ver << endl;
//cout << "left border " << left_border[ver] << " right border " << right_border[ver] << endl;
if (left_child[ver] != -1)
{
depth[left_child[ver]] = depth[ver] + 1;
calc_depth(left_child[ver]);
}
if (right_child[ver] != -1)
{
depth[right_child[ver]] = depth[ver] + 1;
calc_depth(right_child[ver]);
}
}
struct query
{
int l, r, idx;
query(int _l = 0, int _r = 0, int _idx = 0)
{
l = _l;
r = _r;
idx = _idx;
}
};
query task[maxn];
vector < query > spot[maxn];
struct line
{
ll k, m;
line (ll _k = 0, ll _m = 0)
{
k = _k;
m = _m;
}
ll get(ll x)
{
return k * x + m;
}
};
void assign_queries()
{
for (int i = 1; i <= q; i ++)
{
int mx = -1;
for (int j = task[i].l; j <= task[i].r; j ++)
{
if (mx == -1 || depth[j] < depth[mx])
mx = j;
}
spot[mx].push_back(task[i]);
}
}
const ll inf = 1e18;
void chmin(ll &var, ll val)
{
var = min(var, val);
}
struct li_chao_tree
{
struct node
{
line cur;
ll lazy;
bool act;
node *lc, *rc;
node()
{
cur = line();
act = false;
lc = NULL;
rc = NULL;
lazy = 0;
}
};
node *root = NULL;
li_chao_tree()
{
root = new node();
}
void push_lazy(node *ver)
{
if (ver -> act)
ver -> cur.m += ver -> lazy;
if (ver -> lc != NULL)
ver -> lc -> lazy += ver -> lazy;
if (ver -> rc != NULL)
ver -> rc -> lazy += ver -> lazy;
ver -> lazy = 0;
}
void add_line_conscious(node *ver, ll left, ll right, line target)
{
push_lazy(ver);
if (ver -> act == false)
{
ver -> act = true;
ver -> cur = target;
return;
}
ll mid = (left + right) / 2;
if (ver -> cur.get(mid) > target.get(mid))
swap(ver -> cur, target);
if (left == right)
return;
if (ver -> cur.get(left) > target.get(left))
add_line_conscious(ver -> lc, left, mid, target);
if (ver -> cur.get(right) > target.get(right))
add_line_conscious(ver -> rc, mid + 1, right, target);
}
void add_line(node *ver, ll left, ll right, ll qleft, ll qright, line target)
{
push_lazy(ver);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
add_line_conscious(ver, left, right, target);
return;
}
ll mid = (left + right) / 2;
add_line(ver -> lc, left, mid, qleft, qright, target);
add_line(ver -> rc, mid + 1, right, qleft, qright, target);
}
void range_update(node *ver, ll left, ll right, ll qleft, ll qright, ll val)
{
push_lazy(ver);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
ver -> lazy += val;
push_lazy(ver);
return;
}
ll mid = (left + right) / 2;
if (left != right && ver -> act)
{
///cout << "add conscious " << " " << left << " " << mid << " " <<
add_line_conscious(ver -> lc, left, mid, ver -> cur);
add_line_conscious(ver -> rc, mid + 1, right, ver -> cur);
ver -> act = false;
}
range_update(ver -> lc, left, mid, qleft, qright, val);
range_update(ver -> rc, mid + 1, right, qleft, qright, val);
///cout << "range update " << left << " " << right << " " << qleft << " " << qright << " " << ver -> act << endl;
}
ll query_pivot(node *ver, ll left, ll right, ll pivot)
{
push_lazy(ver);
ll mx = inf;
if (ver -> act)
chmin(mx, ver -> cur.get(pivot));
if (left == right)
return mx;
ll mid = (left + right) / 2;
if (pivot <= mid)
chmin(mx, query_pivot(ver -> lc, left, mid, pivot));
else
chmin(mx, query_pivot(ver -> rc, mid + 1, right, pivot));
return mx;
}
void build(node *ver, ll left, ll right)
{
if (left == right)
return;
ver -> lc = new node();
ver -> rc = new node();
ll mid = (left + right) / 2;
build(ver -> lc, left, mid);
build(ver -> rc, mid + 1, right);
}
ll get_pivot(ll pivot)
{
return query_pivot(root, 1, n, pivot);
}
void insert_line(int left, int right, line cur)
{
add_line(root, 1, n, left, right, cur);
}
void add_to_range(int left, int right, ll val)
{
range_update(root, 1, n, left, right, val);
}
};
ll left_price[maxn], right_price[maxn];
li_chao_tree li_left_price, li_right_price;
ll answer[maxn];
void conquer(ll root)
{
line left_line(h[root], - (root - 1) * h[root]), right_line(- h[root], + (root + 1) * h[root]);
if (root != left_border[root])
{
left_line.m += left_price[root - 1];
///left_line.m += li_left_price.get_pivot(root - 1);
}
if (root != right_border[root])
{
right_line.m += right_price[root + 1];
///right_line.m += li_right_price.get_pivot(root + 1);
}
if (root == left_border[root])
{
///cout << "conquer " << h[root] << endl;
li_left_price.insert_line(root, root, line(0, h[root]));
left_price[root] = h[root];
}
else
{
li_left_price.insert_line(root, root, line(0, li_left_price.get_pivot(root - 1) + h[root]));
left_price[root] = left_price[root - 1] + h[root];
}
//if (root == 1)
//cout << "first " << li_left_price.get_pivot(2) << endl;
li_left_price.add_to_range(root + 1, right_border[root], (root - left_border[root] + 1) * h[root]);
li_left_price.insert_line(root + 1, right_border[root], left_line);
for (int pivot = root + 1; pivot <= right_border[root]; pivot ++)
{
left_price[pivot] += (root - left_border[root] + 1) * h[root];
chmin(left_price[pivot], left_line.get(pivot));
}
if (root == right_border[root])
{
li_right_price.insert_line(root, root, line(0, h[root]));
right_price[root] = h[root];
}
else
{
li_right_price.insert_line(root, root, line(0, li_right_price.get_pivot(root + 1) + h[root]));
right_price[root] = right_price[root + 1] + h[root];
}
li_right_price.add_to_range(left_border[root], root - 1, (right_border[root] - root + 1) * h[root]);
li_right_price.insert_line(left_border[root], root - 1, right_line);
for (int pivot = root - 1; pivot >= left_border[root]; pivot --)
{
right_price[pivot] += (right_border[root] - root + 1) * h[root];
chmin(right_price[pivot], right_line.get(pivot));
}
}
void divide(int root)
{
if (left_child[root] != -1)
divide(left_child[root]);
if (right_child[root] != -1)
divide(right_child[root]);
for (query cur : spot[root])
{
///cout << "answer " << left_border[root] << " " << right_border[root] << " " << cur.idx << endl;
//ll left_opt = li_right_price.get_pivot(cur.l) + (ll)(cur.r - root + 1) * h[root];
ll left_opt = right_price[cur.l] + (ll)(cur.r - root + 1) * h[root];
//ll right_opt = (ll)(root - cur.l + 1) * h[root] + li_left_price.get_pivot(cur.r);
ll right_opt = (ll)(root - cur.l + 1) * h[root] + left_price[cur.r];
chmin(answer[cur.idx], min(left_opt, right_opt));
}
conquer(root);
/**cout << "range " << left_border[root] << " " << right_border[root] << endl;
for (int i = left_border[root]; i <= right_border[root]; i ++ )
cout << li_left_price.get_pivot(i) << " ";
cout << endl;
for (int i = left_border[root]; i <= right_border[root]; i ++ )
cout << li_right_price.get_pivot(i) << " ";
cout << endl;
cout << "-------------" << endl;
for (int i = left_border[root]; i <= right_border[root]; i ++ )
cout << left_price[i] << " ";
cout << endl;
for (int i = left_border[root]; i <= right_border[root]; i ++ )
cout << right_price[i] << " ";
cout << endl;*/
for (int i = left_border[root]; i <= right_border[root]; i ++)
{
if (li_left_price.get_pivot(i) != left_price[i])
{
assert(false);
}
if (li_right_price.get_pivot(i) != right_price[i])
{
assert(false);
}
}
}
vector < ll > get_result()
{
vector < ll > res;
for (int i = 1; i <= q; i ++)
res.push_back(answer[i]);
return res;
}
void build_li_chao()
{
li_left_price.build(li_left_price.root, 1, n);
li_right_price.build(li_right_price.root, 1, n);
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,
vector<int> R)
{
n = H.size();
q = L.size();
for (int i = 1; i <= n; i ++)
{
h[i] = H[i - 1];
}
for (int i = 1; i <= q; i ++)
{
task[i] = query(L[i - 1] + 1, R[i - 1] + 1, i);
answer[i] = inf;
}
cartesian_tree();
calc_depth(root);
assign_queries();
build_li_chao();
divide(root);
vector < ll > res = get_result();
return res;
}
/**
5 1
3 1 5 4 3
1 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
41308 KB |
Output is correct |
| 2 |
Correct |
19 ms |
44124 KB |
Output is correct |
| 3 |
Correct |
19 ms |
44124 KB |
Output is correct |
| 4 |
Correct |
21 ms |
44120 KB |
Output is correct |
| 5 |
Correct |
22 ms |
44124 KB |
Output is correct |
| 6 |
Correct |
306 ms |
44400 KB |
Output is correct |
| 7 |
Correct |
21 ms |
42076 KB |
Output is correct |
| 8 |
Correct |
301 ms |
44452 KB |
Output is correct |
| 9 |
Correct |
125 ms |
44360 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
41308 KB |
Output is correct |
| 2 |
Correct |
19 ms |
44124 KB |
Output is correct |
| 3 |
Correct |
19 ms |
44124 KB |
Output is correct |
| 4 |
Correct |
21 ms |
44120 KB |
Output is correct |
| 5 |
Correct |
22 ms |
44124 KB |
Output is correct |
| 6 |
Correct |
306 ms |
44400 KB |
Output is correct |
| 7 |
Correct |
21 ms |
42076 KB |
Output is correct |
| 8 |
Correct |
301 ms |
44452 KB |
Output is correct |
| 9 |
Correct |
125 ms |
44360 KB |
Output is correct |
| 10 |
Correct |
51 ms |
45136 KB |
Output is correct |
| 11 |
Correct |
96 ms |
44976 KB |
Output is correct |
| 12 |
Correct |
53 ms |
45140 KB |
Output is correct |
| 13 |
Correct |
104 ms |
45004 KB |
Output is correct |
| 14 |
Correct |
848 ms |
45396 KB |
Output is correct |
| 15 |
Correct |
47 ms |
45016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
41304 KB |
Output is correct |
| 2 |
Correct |
2690 ms |
50392 KB |
Output is correct |
| 3 |
Execution timed out |
5517 ms |
51856 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
41304 KB |
Output is correct |
| 2 |
Correct |
2690 ms |
50392 KB |
Output is correct |
| 3 |
Execution timed out |
5517 ms |
51856 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
41308 KB |
Output is correct |
| 2 |
Correct |
19 ms |
44124 KB |
Output is correct |
| 3 |
Correct |
19 ms |
44124 KB |
Output is correct |
| 4 |
Correct |
21 ms |
44120 KB |
Output is correct |
| 5 |
Correct |
22 ms |
44124 KB |
Output is correct |
| 6 |
Correct |
306 ms |
44400 KB |
Output is correct |
| 7 |
Correct |
21 ms |
42076 KB |
Output is correct |
| 8 |
Correct |
301 ms |
44452 KB |
Output is correct |
| 9 |
Correct |
125 ms |
44360 KB |
Output is correct |
| 10 |
Correct |
51 ms |
45136 KB |
Output is correct |
| 11 |
Correct |
96 ms |
44976 KB |
Output is correct |
| 12 |
Correct |
53 ms |
45140 KB |
Output is correct |
| 13 |
Correct |
104 ms |
45004 KB |
Output is correct |
| 14 |
Correct |
848 ms |
45396 KB |
Output is correct |
| 15 |
Correct |
47 ms |
45016 KB |
Output is correct |
| 16 |
Correct |
9 ms |
41304 KB |
Output is correct |
| 17 |
Correct |
2690 ms |
50392 KB |
Output is correct |
| 18 |
Execution timed out |
5517 ms |
51856 KB |
Time limit exceeded |
| 19 |
Halted |
0 ms |
0 KB |
- |
