#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define arr3 array<int, 3>
const ll inf = 1e18;
struct DS{
struct line{
ll k, b;
ll operator ()(ll x){
return k * x + b;
}
line(ll ks, ll bs){
k = ks; b = bs;
}
};
vector<line> t;
vector<pll> p;
int n;
vector<ll> a;
DS(int ns){
n = ns;
t.assign(4 * n, {0, inf});
p.resize(4 * n);
}
void apply(int v, pll x){
t[v].k += x.ff; t[v].b += x.ss;
p[v].ff += x.ff; p[v].ss += x.ss;
}
void push1(int& v, int& tl, int& tr){
int vv = 2 * v;
apply(vv, p[v]); apply(vv + 1, p[v]);
p[v] = {0, 0};
}
void push2(int& v, int& tl, int& tr){
if (t[v].b == inf) return;
int vv = 2 * v, tm = (tl + tr) / 2;
insert(vv, tl, tm, t[v]);
insert(vv + 1, tm + 1, tr, t[v]);
t[v] = {0, inf};
}
void insert(int v, int tl, int tr, line f){
if (tl == tr){
if (t[v](tl) > f(tl)) t[v] = f;
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
push1(v, tl, tr);
if (t[v].k > f.k) swap(t[v], f);
if (f(tm) <= t[v](tm)){
swap(t[v], f);
insert(vv + 1, tm + 1, tr, f);
}
else {
insert(vv, tl, tm, f);
}
}
void chmin(int v, int tl, int tr, int& l, int& r, line& f){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
insert(v, tl, tr, f);
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
push1(v, tl, tr);
chmin(vv, tl, tm, l, r, f);
chmin(vv + 1, tm + 1, tr, l, r, f);
}
void chmin(int l, int r, int k, ll b){
line f(k, b);
chmin(1, 1, n, l, r, f);
}
void add(int v, int tl, int tr, int& l, int& r, line& f){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
apply(v, {f.k, f.b});
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
push1(v, tl, tr);
push2(v, tl, tr);
add(vv, tl, tm, l, r, f);
add(vv + 1, tm + 1, tr, l, r, f);
}
void add(int l, int r, ll x){
line f(0, x);
add(1, 1, n, l, r, f);
}
ll get(int v, int tl, int tr, int& x){
if (tl == tr) return t[v](x);
int tm = (tl + tr) / 2, vv = 2 * v;
push1(v, tl, tr);
if (x <= tm){
return min(t[v](x), get(vv, tl, tm, x));
}
return min(t[v](x), get(vv + 1, tm + 1, tr, x));
}
ll get(int x){
return get(1, 1, n, x);
}
};
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
const int A = 1e9;
int n = (int) H.size(), q = (int) L.size();
vector<int> h(n + 1);
map<int, vector<int>> d;
for (int i = 1; i <= n; i++){
h[i] = H[i - 1];
d[h[i]].pb(i);
}
vector<int> log(n + 1);
for (int i = 2; i <= n; i++) log[i] = log[i / 2] + 1;
const int lg = log[n];
vector<vector<int>> pw(n + 1, vector<int>(lg + 1)), pw1(n + 1, vector<int>(lg + 1, A));
for (int i = 1; i <= n; i++) pw[i][0] = pw1[i][0] = h[i];
for (int j = 1; j <= lg; j++){
for (int i = 1; i + (1 << j) <= n + 1; i++){
pw[i][j] = max(pw[i][j - 1], pw[i + (1 << (j - 1))][j - 1]);
pw1[i][j] = min(pw1[i][j - 1], pw1[i + (1 << (j - 1))][j - 1]);
}
}
auto get = [&](int l, int r){
int k = log[r - l + 1];
return max(pw[l][k], pw[r - (1 << k) + 1][k]);
};
auto getm = [&](int l, int r){
int k = log[r - l + 1];
return min(pw1[l][k], pw1[r - (1 << k) + 1][k]);
};
vector<int> :: iterator it;
auto pp = [&](int x, int l, int r){
vector<int> f;
it = lower_bound(d[x].begin(), d[x].end(), l);
while (it != d[x].end() && (*it) <= r){
f.pb((*it));
it++;
}
return f;
};
auto gp = [&](int x, int l, int r){
vector<int> f = pp(x, l, r);
vector<pii> all;
int pre = l;
for (int i: f){
if (pre < i){
all.pb({pre, i - 1});
}
pre = i + 1;
}
if (pre <= r) all.pb({pre, r});
return all;
};
map<int, vector<pii>> mp;
function<void(int, int)> build1 = [&](int l, int r){
int m = get(l, r);
mp[m].push_back({l, r});
vector<pii> all = gp(m, l, r);
for (auto [l1, r1]: all){
build1(l1, r1);
}
};
build1(1, n);
vector<ll> out(q + 1);
map<pii, vector<arr3>> qs;
for (int i = 1; i <= q; i++){
int l, r;
l = L[i - 1]; r = R[i - 1];
l++; r++;
if (get(l, r) == getm(l, r)){
out[i] = 1LL * h[l] * (r - l + 1);
continue;
}
int k = get(l, r), l1 = 0, r1 = (int) mp[k].size() - 1;
vector<pii>& V = mp[k];
while (l1 + 1 < r1){
int m = (l1 + r1) / 2;
if (V[m].ff <= l){
l1 = m;
}
else {
r1 = m - 1;
}
}
if (V[r1].ff <= l) l1 = r1;
qs[V[l1]].pb({l, r, i});
}
DS T1(n), T2(n);
vector<int> :: iterator it1, it2;
function<void(int, int)> build = [&](int l, int r){
int m = get(l, r);
vector<pii> all = gp(m, l, r);
for (auto [l1, r1]: all) build(l1, r1);
if (all.empty()){
for (int i = l; i <= r; i++){
T1.add(i, i, 1LL * m * (i - l + 1));
T2.add(i, i, 1LL * m * (r - i + 1));
}
}
for (auto [l1, r1]: all){
int m1 = get(l1, r1);
vector<pii> all1 = gp(m1, l1, r1);
ll mn = inf;
for (auto [l2, r2]: all1){
// f(l1, i) = min(mn + m1 * (i - l1), f(l2, i) + m1 * (l2 - l1));
ll F = T1.get(r2);
T1.add(l2, r2, 1LL * m1 * (l2 - l1));
if (mn != inf) T1.chmin(l2, r2, m1, mn - 1LL * m1 * l1);
mn = min(mn, F - 1LL * m1 * (r2 - l2));
}
reverse(all1.begin(), all1.end());
mn = inf;
for (auto [l2, r2]: all1){
// f(i, r1) = min(mn + m1 * (r1 - i), f(i, r2) + m1 * (r1 - r2));
ll F = T2.get(l2);
T2.add(l2, r2, 1LL * m1 * (r1 - r2));
if (mn != inf) T2.chmin(l2, r2, -m1, mn + 1LL * m1 * r1);
mn = min(mn, F - 1LL * m1 * (r2 - l2));
}
vector<int> f1 = pp(m1, l1, r1);
for (int i: f1){
T1.add(i, i, -T1.get(i));
ll mn = 1LL * m1 * (i - l1 + 1);
if (i != l1) mn = min(mn, T1.get(i - 1) + m1);
T1.add(i, i, mn);
}
reverse(f1.begin(), f1.end());
for (int i: f1){
T2.add(i, i, -T2.get(i));
ll mn = 1LL * m1 * (r1 - i + 1);
if (i != r1) mn = min(mn, T2.get(i + 1) + m1);
T2.add(i, i, mn);
}
}
if (all.empty()) return;
vector<int> x1, y1;
for (auto [l1, r1]: all){
x1.pb(l1); y1.pb(r1);
}
int N = (int) all.size(), LG = log2(N);
vector<vector<ll>> sp(N + 1, vector<ll>(LG + 1, inf));
for (int i = 1; i <= N; i++) sp[i][0] = (T1.get(all[i - 1].ss) - 1LL * m * (all[i - 1].ss - all[i - 1].ff));
for (int j = 1; j <= LG; j++){
for (int i = 1; i + (1 << j) <= N + 1; i++){
sp[i][j] = min(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
}
}
auto gets = [&](int l, int r){
if (l > r) return inf;
int k = log[r - l + 1];
return min(sp[l][k], sp[r - (1 << k) + 1][k]);
};
for (auto [ql, qr, i]: qs[{l, r}]){
it1 = lower_bound(x1.begin(), x1.end(), ql);
it2 = upper_bound(y1.begin(), y1.end(), qr); it2--;
int i1 = (int) (it1 - x1.begin()), i2 = (int) (it2 - y1.begin());
out[i] = gets(i1 + 1, i2 + 1);
if (out[i] != inf) out[i] += 1LL * m * (qr - ql);
if (i1 > 0){
i1--;
if (all[i1].ss >= ql){
out[i] = min(out[i], T2.get(ql) + 1LL * m * (qr - all[i1].ss));
}
}
if (it2 != prev(y1.end())){
i2++;
if (all[i2].ff <= qr){
out[i] = min(out[i], T1.get(qr) + 1LL * m * (all[i2].ff - ql));
}
}
}
};
build(1, n);
vector<ll> ret;
for (int i = 1; i <= q; i++) ret.pb(out[i]);
return ret;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
2556 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
2556 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
30 ms |
7124 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
30 ms |
7124 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
2556 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
