#include "meetings.h"
#include <bits/stdc++.h>
using i64 = long long;
constexpr int inf = 1 << 30;
template <class M>
class LazySegmentTree {
using T = typename M::T;
using L = typename M::L;
int n, logn, size;
std::vector<T> data;
std::vector<L> lazy;
void update(int i) {
data[i] = M::op(data[2 * i], data[2 * i + 1]);
}
void all_apply(int i, const L &f) {
data[i] = M::map(f, data[i]);
if (i < size) lazy[i] = M::composite(f, lazy[i]);
}
void push(int i) {
all_apply(2 * i, lazy[i]);
all_apply(2 * i + 1, lazy[i]);
lazy[i] = M::id();
}
public:
LazySegmentTree(const std::vector<T> &vec) : n(vec.size()) {
logn = 1;
while ((1 << logn) < n) ++logn;
size = 1 << logn;
data.assign(2 * size, M::e());
lazy.assign(size, M::id());
std::copy(vec.begin(), vec.end(), data.begin() + size);
for (int i = size - 1; i > 0; --i) update(i);
}
void apply(int l, int r, const L &f) {
l += size, r += size;
for (int d = logn; d >= 1; --d) {
if (((l >> d) << d) != l) push(l >> d);
if (((r >> d) << d) != r) push((r - 1) >> d);
}
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l /= 2;
r /= 2;
}
l = l2, r = r2;
for (int d = 1; d <= logn; ++d) {
if (((l >> d) << d) != l) update(l >> d);
if (((r >> d) << d) != r) update((r - 1) >> d);
}
}
T fold(int l, int r) {
l += size, r += size;
for (int d = logn; d >= 1; --d) {
if (((l >> d) << d) != l) push(l >> d);
if (((r >> d) << d) != r) push((r - 1) >> d);
}
T pl = M::e(), pr = M::e();
while (l < r) {
if (l & 1) pl = M::op(pl, data[l++]);
if (r & 1) pr = M::op(data[--r], pr);
l /= 2;
r /= 2;
}
return M::op(pl, pr);
}
};
struct Mon {
using T = int;
static T op(T a, T b) {
return std::max(a, b);
}
static T e() {
return -inf;
}
using L = int;
static T map(L a, T b) {
return a + b;
}
static L composite(L a, T b) {
return a + b;
}
static L id() {
return 0;
}
};
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
int N = (int)H.size(), Q = (int)L.size();
const int maxH = *std::max_element(H.begin(), H.end());
assert(maxH <= 20);
for (auto &e : H) --e;
std::vector<std::vector<std::pair<int, int>>> ranges(maxH);
std::vector<int> initVec(N + 1);
for (int x = 0; x < maxH; ++x) {
int l = 0;
for (int i = 0; i < N; ++i) {
if (H[i] >= x) {
if (l != i) {
ranges[x].push_back({l, i - 1});
}
l = i + 1;
}
}
if (l != N) ranges[x].push_back({l, N - 1});
for (const auto &[l, r] : ranges[x]) {
initVec[l] += r - l + 1;
initVec[r + 1] -= r - l + 1;
}
}
for (int i = 0; i < N; ++i) initVec[i + 1] += initVec[i];
initVec.pop_back();
LazySegmentTree<Mon> seg(initVec);
std::vector<i64> answer(Q);
for (int i = 0; i < Q; ++i) {
auto fixL = [&](int l, const std::pair<int, int> &range) {
if (range.first >= l or range.second < l) return;
seg.apply(l, range.second + 1, -(l - range.first));
};
auto fixR = [&](int r, const std::pair<int, int> &range) {
if (range.first > r or range.second <= r) return;
seg.apply(range.first, r + 1, -(range.second - r));
};
for (int x = 0; x < maxH; ++x) {
auto itr = std::lower_bound(ranges[x].begin(), ranges[x].end(), std::make_pair(L[i], 0));
if (itr != ranges[x].begin()) {
--itr;
fixL(L[i], *itr);
}
itr = std::lower_bound(ranges[x].begin(), ranges[x].end(), std::make_pair(R[i] + 1, 0));
if (itr != ranges[x].begin()) {
--itr;
fixR(R[i], *itr);
}
}
answer[i] = (R[i] - L[i] + 1) * maxH - seg.fold(L[i], R[i] + 1);
auto revL = [&](int l, const std::pair<int, int> &range) {
if (range.first >= l or range.second < l) return;
seg.apply(l, range.second + 1, l - range.first);
};
auto revR = [&](int r, const std::pair<int, int> &range) {
if (range.first > r or range.second <= r) return;
seg.apply(range.first, r + 1, range.second - r);
};
for (int x = 0; x < maxH; ++x) {
auto itr = std::lower_bound(ranges[x].begin(), ranges[x].end(), std::make_pair(L[i], 0));
if (itr != ranges[x].begin()) {
--itr;
revL(L[i], *itr);
}
itr = std::lower_bound(ranges[x].begin(), ranges[x].end(), std::make_pair(R[i] + 1, 0));
if (itr != ranges[x].begin()) {
--itr;
revR(R[i], *itr);
}
}
}
return answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
52 ms |
1672 KB |
Output is correct |
| 3 |
Correct |
168 ms |
7700 KB |
Output is correct |
| 4 |
Correct |
219 ms |
7372 KB |
Output is correct |
| 5 |
Correct |
134 ms |
7624 KB |
Output is correct |
| 6 |
Correct |
137 ms |
7320 KB |
Output is correct |
| 7 |
Correct |
146 ms |
7372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
52 ms |
1672 KB |
Output is correct |
| 3 |
Correct |
168 ms |
7700 KB |
Output is correct |
| 4 |
Correct |
219 ms |
7372 KB |
Output is correct |
| 5 |
Correct |
134 ms |
7624 KB |
Output is correct |
| 6 |
Correct |
137 ms |
7320 KB |
Output is correct |
| 7 |
Correct |
146 ms |
7372 KB |
Output is correct |
| 8 |
Correct |
1463 ms |
10104 KB |
Output is correct |
| 9 |
Correct |
1138 ms |
10104 KB |
Output is correct |
| 10 |
Correct |
1588 ms |
10116 KB |
Output is correct |
| 11 |
Correct |
1590 ms |
9984 KB |
Output is correct |
| 12 |
Correct |
1243 ms |
9976 KB |
Output is correct |
| 13 |
Correct |
1576 ms |
9984 KB |
Output is correct |
| 14 |
Correct |
840 ms |
11528 KB |
Output is correct |
| 15 |
Correct |
2228 ms |
8632 KB |
Output is correct |
| 16 |
Correct |
1536 ms |
7368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
