#include <bits/stdc++.h>
int n;
std::vector <int> h, L, R;
std::vector <int> mxl, mxr;
struct Lift {
std::vector <std::vector <std::pair <int, long long>>> bnl, bnr;
void init() {
bnl.resize(19, std::vector <std::pair <int, long long>> (n, { -1, 0 }));
bnr.resize(19, std::vector <std::pair <int, long long>> (n, { -1, 0 }));
for (int i = 0; i < n; i++) {
if (mxl[i] != -1) bnl[0][i] = { mxl[i], (long long) h[mxl[i]] * (i - mxl[i]) };
if (mxr[i] != -1) bnr[0][i] = { mxr[i], (long long) h[mxr[i]] * (mxr[i] - i) };
}
for (int b = 1; b < 19; b++) {
for (int i = 0; i < n; i++) {
if (bnl[b - 1][i].first != -1 && bnl[b - 1][bnl[b - 1][i].first].first != -1) {
bnl[1 << b][i] = {
bnl[b - 1][bnl[b - 1][i].first].first,
bnl[b - 1][i].second + bnl[b - 1][bnl[b - 1][i].first].second
};
}
if (bnr[b - 1][i].first != -1 && bnr[b - 1][bnr[b - 1][i].first].first != -1) {
bnr[b][i] = {
bnr[b - 1][bnr[b - 1][i].first].first,
bnr[b - 1][i].second + bnr[b - 1][bnr[b - 1][i].first].second
};
}
}
}
}
long long query(int ind, int l, int r) {
long long res = h[ind];
int li = ind, ri = ind;
for (int b = 18; ~b; b--) {
if (bnl[b][li].first == -1 || bnl[b][li].first < l) continue;
res += bnl[b][li].second, li = bnl[b][li].first;
}
for (int b = 18; ~b; b--) {
if (bnr[b][ri].first == -1 || bnr[b][ri].first > r) continue;
res += bnr[b][ri].second, ri = bnr[b][ri].first;
}
if (li != l) res += (long long) (li - l) * h[li];
if (ri != r) res += (long long) (r - ri) * h[ri];
return res;
}
};
Lift lift;
struct Sparse {
std::vector <std::vector <int>> bin;
int merge(std::vector <int> i, int l, int r) {
long long bst = 1LL << 60;
int ind = -1;
for (int x : i) {
long long val = lift.query(x, l, r);
if (val < bst) bst = val, ind = x;
}
return ind;
}
void init() {
bin.resize(19, std::vector <int> (n, -1));
std::iota(bin[0].begin(), bin[0].end(), 0);
for (int b = 1; b < 19; b++) {
for (int i = 0; i + (1 << b) - 1 < n; i++) {
std::vector <int> ind = {
bin[b - 1][i],
bin[b - 1][i + (1 << (b - 1))],
i + (1 << (b - 1)) - 1,
i + (1 << (b - 1))
};
bin[b][i] = merge(ind, i, i + (1 << b) - 1);
}
}
}
long long query(int l, int r) {
if (l == r) return h[l];
int b = 31 - __builtin_clz(r - l + 1);
std::vector <int> ind = {
bin[b][l],
bin[b][r - (1 << b) + 1],
l + (1 << b) - 1,
r - (1 << b) + 1
};
int index = merge(ind, l, r);
return lift.query(index, l, r);
}
};
Sparse sparse;
std::vector <long long> minimum_costs(std::vector <int> H, std::vector <int> _L, std::vector <int> _R) {
n = H.size();
h = H, L = _L, R = _R;
mxl.resize(n, -1);
mxr.resize(n, -1);
std::vector <int> ord(n);
std::iota(ord.begin(), ord.end(), 0);
std::sort(ord.begin(), ord.end(), [&] (int u, int v) { return h[u] > h[v]; });
std::set <int> st;
for (int i : ord) {
auto it = st.lower_bound(i);
if (it != st.end()) mxr[i] = *it;
if (it != st.begin()) mxl[i] = *(--it);
st.insert(i);
}
lift.init();
sparse.init();
std::vector <long long> res(L.size(), -1);
for (int i = 0; i < (int) L.size(); i++) {
int l = L[i], r = R[i];
res[i] = sparse.query(l, r);
}
return res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
4436 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
4436 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
17 ms |
13780 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
17 ms |
13780 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Runtime error |
4 ms |
4436 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
