#include "meetings.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, N = 750005;
const ll oo = 1e18;
int n, q;
bool f = false;
pi max2(pi a, pi b) {
if(a.F != b.F) return max(a, b);
return min(a, b);
}
pi st[N][20];
int argmax(int L, int R) { // [L, R]
int k = __lg(R - L + 1);
if(f)
return max2(st[L][k], st[R - (1 << k) + 1][k]).S;
else
return max(st[L][k], st[R - (1 << k) + 1][k]).S;
};
ll ans[N];
vi G[N];
namespace segtree {
struct node {
ll l_val, r_val;
ll m, b;
ll lz;
int tl, tr;
node(ll val = 0) {
l_val = r_val = val;
m = b = lz = 0;
}
} t[N * 4];
void pull(int v) {
t[v].l_val = t[v * 2].l_val;
t[v].r_val = t[v * 2 + 1].r_val;
}
void apply_add(int v, ll x) {
t[v].l_val += x, t[v].r_val += x;
if(t[v].m) {
t[v].b += x;
} else {
t[v].lz += x;
}
}
void apply_set(int v, ll m, ll b) {
t[v].l_val = t[v].tl * m + b;
t[v].r_val = (t[v].tr - 1) * m + b;
t[v].m = m, t[v].b = b;
t[v].lz = 0;
}
void push(int v) {
if(t[v].m) { // set
apply_set(v * 2, t[v].m, t[v].b);
apply_set(v * 2 + 1, t[v].m, t[v].b);
t[v].m = t[v].b = 0;
} else { // add
apply_add(v * 2, t[v].lz);
apply_add(v * 2 + 1, t[v].lz);
t[v].lz = 0;
}
}
void build(int v = 1, int tl = 0, int tr = n) {
t[v] = node();
t[v].tl = tl, t[v].tr = tr;
if(tr - tl == 1)
return;
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm, tr);
}
void add(int l, int r, ll x, int v = 1, int tl = 0, int tr = n) {
if(l <= tl && tr <= r) {
apply_add(v, x);
return;
}
push(v);
int tm = (tl + tr) / 2;
if(l < tm) add(l, r, x, v * 2, tl, tm);
if(r > tm) add(l, r, x, v * 2 + 1, tm, tr);
pull(v);
}
ll qry(int pos, int v = 1, int tl = 0, int tr = n) {
if(tr - tl == 1)
return t[v].l_val;
push(v);
int tm = (tl + tr) / 2;
if(pos < tm) return qry(pos, v * 2, tl, tm);
else return qry(pos, v * 2 + 1, tm, tr);
}
void cmin(int l, int r, ll m, ll b, int v = 1, int tl = 0, int tr = n) {
if(l <= tl && tr <= r) {
if(t[v].r_val >= m * (tr - 1) + b) {
apply_set(v, m, b);
return;
}
if(t[v].l_val <= m * tl + b)
return;
}
push(v);
int tm = (tl + tr) / 2;
if(l < tm) cmin(l, r, m, b, v * 2, tl, tm);
if(r > tm) cmin(l, r, m, b, v * 2 + 1, tm, tr);
pull(v);
}
} // segtree
using namespace segtree;
int h[N], l[N], r[N];
void dfs(int L, int R) { // [L, R]
if(L > R) return;
int m = argmax(L, R);
dfs(L, m - 1), dfs(m + 1, R);
for(int i:G[m]) {
ll cur = 1LL * (m - l[i] + 1) * h[m];
assert(L <= l[i] && r[i] <= R);
if(r[i] > m) cur += qry(r[i]);
ans[i] = min(ans[i], cur);
}
add(m, R + 1, 1LL * (m - L + 1) * h[m]);
if(L < m)
cmin(m, R + 1, h[m], qry(m - 1) - 1LL * h[m] * (m - 1));
}
void solve() {
for(int i = 0; i < n; i++)
st[i][0] = {h[i], i};
for(int j = 1; j < 20; j++)
for(int i = 0; i + (1 << j) - 1 < n; i++) {
if(f)
st[i][j] = max2(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
else
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
for(int i = 0; i < q; i++)
G[argmax(l[i], r[i])].PB(i);
build();
dfs(0, n - 1);
for(int i = 0; i < n; i++)
G[i].clear();
}
V<ll> minimum_costs(vi _h, vi _l, vi _r) {
n = SZ(_h), q = SZ(_l);
for(int i = 0; i < n; i++) h[i] = _h[i];
for(int i = 0; i < q; i++) l[i] = _l[i], r[i] = _r[i], ans[i] = oo;
solve();
reverse(h, h + n);
for(int i = 0; i < q; i++) {
swap(l[i], r[i]);
l[i] = n - l[i] - 1, r[i] = n - r[i] - 1;
}
f = true;
solve();
V<ll> tt;
for(int i = 0; i < q; i++)
tt.PB(ans[i]);
return tt;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
158736 KB |
Output is correct |
2 |
Correct |
71 ms |
159244 KB |
Output is correct |
3 |
Correct |
74 ms |
159396 KB |
Output is correct |
4 |
Correct |
69 ms |
159364 KB |
Output is correct |
5 |
Correct |
71 ms |
159324 KB |
Output is correct |
6 |
Correct |
72 ms |
159492 KB |
Output is correct |
7 |
Correct |
73 ms |
159332 KB |
Output is correct |
8 |
Correct |
75 ms |
159444 KB |
Output is correct |
9 |
Correct |
66 ms |
159392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
158736 KB |
Output is correct |
2 |
Correct |
71 ms |
159244 KB |
Output is correct |
3 |
Correct |
74 ms |
159396 KB |
Output is correct |
4 |
Correct |
69 ms |
159364 KB |
Output is correct |
5 |
Correct |
71 ms |
159324 KB |
Output is correct |
6 |
Correct |
72 ms |
159492 KB |
Output is correct |
7 |
Correct |
73 ms |
159332 KB |
Output is correct |
8 |
Correct |
75 ms |
159444 KB |
Output is correct |
9 |
Correct |
66 ms |
159392 KB |
Output is correct |
10 |
Correct |
72 ms |
160128 KB |
Output is correct |
11 |
Correct |
74 ms |
160112 KB |
Output is correct |
12 |
Correct |
71 ms |
160088 KB |
Output is correct |
13 |
Correct |
72 ms |
160156 KB |
Output is correct |
14 |
Correct |
77 ms |
160392 KB |
Output is correct |
15 |
Correct |
83 ms |
160136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
158796 KB |
Output is correct |
2 |
Correct |
106 ms |
163720 KB |
Output is correct |
3 |
Correct |
392 ms |
187512 KB |
Output is correct |
4 |
Correct |
359 ms |
182028 KB |
Output is correct |
5 |
Correct |
354 ms |
188584 KB |
Output is correct |
6 |
Correct |
367 ms |
189252 KB |
Output is correct |
7 |
Correct |
345 ms |
190300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
158796 KB |
Output is correct |
2 |
Correct |
106 ms |
163720 KB |
Output is correct |
3 |
Correct |
392 ms |
187512 KB |
Output is correct |
4 |
Correct |
359 ms |
182028 KB |
Output is correct |
5 |
Correct |
354 ms |
188584 KB |
Output is correct |
6 |
Correct |
367 ms |
189252 KB |
Output is correct |
7 |
Correct |
345 ms |
190300 KB |
Output is correct |
8 |
Correct |
345 ms |
182476 KB |
Output is correct |
9 |
Correct |
300 ms |
182276 KB |
Output is correct |
10 |
Correct |
385 ms |
182464 KB |
Output is correct |
11 |
Correct |
360 ms |
181848 KB |
Output is correct |
12 |
Correct |
331 ms |
181672 KB |
Output is correct |
13 |
Correct |
367 ms |
182120 KB |
Output is correct |
14 |
Correct |
385 ms |
187968 KB |
Output is correct |
15 |
Correct |
350 ms |
181888 KB |
Output is correct |
16 |
Correct |
361 ms |
188012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
62 ms |
158736 KB |
Output is correct |
2 |
Correct |
71 ms |
159244 KB |
Output is correct |
3 |
Correct |
74 ms |
159396 KB |
Output is correct |
4 |
Correct |
69 ms |
159364 KB |
Output is correct |
5 |
Correct |
71 ms |
159324 KB |
Output is correct |
6 |
Correct |
72 ms |
159492 KB |
Output is correct |
7 |
Correct |
73 ms |
159332 KB |
Output is correct |
8 |
Correct |
75 ms |
159444 KB |
Output is correct |
9 |
Correct |
66 ms |
159392 KB |
Output is correct |
10 |
Correct |
72 ms |
160128 KB |
Output is correct |
11 |
Correct |
74 ms |
160112 KB |
Output is correct |
12 |
Correct |
71 ms |
160088 KB |
Output is correct |
13 |
Correct |
72 ms |
160156 KB |
Output is correct |
14 |
Correct |
77 ms |
160392 KB |
Output is correct |
15 |
Correct |
83 ms |
160136 KB |
Output is correct |
16 |
Correct |
62 ms |
158796 KB |
Output is correct |
17 |
Correct |
106 ms |
163720 KB |
Output is correct |
18 |
Correct |
392 ms |
187512 KB |
Output is correct |
19 |
Correct |
359 ms |
182028 KB |
Output is correct |
20 |
Correct |
354 ms |
188584 KB |
Output is correct |
21 |
Correct |
367 ms |
189252 KB |
Output is correct |
22 |
Correct |
345 ms |
190300 KB |
Output is correct |
23 |
Correct |
345 ms |
182476 KB |
Output is correct |
24 |
Correct |
300 ms |
182276 KB |
Output is correct |
25 |
Correct |
385 ms |
182464 KB |
Output is correct |
26 |
Correct |
360 ms |
181848 KB |
Output is correct |
27 |
Correct |
331 ms |
181672 KB |
Output is correct |
28 |
Correct |
367 ms |
182120 KB |
Output is correct |
29 |
Correct |
385 ms |
187968 KB |
Output is correct |
30 |
Correct |
350 ms |
181888 KB |
Output is correct |
31 |
Correct |
361 ms |
188012 KB |
Output is correct |
32 |
Correct |
2700 ms |
327740 KB |
Output is correct |
33 |
Correct |
2130 ms |
323960 KB |
Output is correct |
34 |
Correct |
2505 ms |
327700 KB |
Output is correct |
35 |
Correct |
2741 ms |
326984 KB |
Output is correct |
36 |
Correct |
2114 ms |
327548 KB |
Output is correct |
37 |
Correct |
2492 ms |
327908 KB |
Output is correct |
38 |
Correct |
2950 ms |
372068 KB |
Output is correct |
39 |
Correct |
3139 ms |
371936 KB |
Output is correct |
40 |
Correct |
2915 ms |
332136 KB |
Output is correct |
41 |
Correct |
3099 ms |
406448 KB |
Output is correct |
42 |
Correct |
3131 ms |
405544 KB |
Output is correct |
43 |
Correct |
3047 ms |
405564 KB |
Output is correct |
44 |
Correct |
3480 ms |
371424 KB |
Output is correct |