#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxN=7.5e5;
int n, q;
array<int, 2> a[20][mxN];
vector<ll> ans;
vector<int> ta[mxN], ql, qr;
array<ll, 2> st[1<<21], lz[1<<21];
array<int, 2> lca(int l, int r) {
int k=31-__builtin_clz(r-l+1);
return max(a[k][l], a[k][r-(1<<k)+1]);
}
void app(int i, array<ll, 2> x, int l2, int r2) {
if(x[0]) {
st[i]={l2*x[0], r2*x[0]};
lz[i]={x[0], 0};
}
st[i][0]+=x[1];
st[i][1]+=x[1];
lz[i][1]+=x[1];
}
void psh(int i, int l2, int m2, int r2) {
app(2*i, lz[i], l2, m2);
app(2*i+1, lz[i], m2+1, r2);
lz[i]={};
}
void upd(int l1, int r1, array<ll, 2> x, bool f, int i=1, int l2=0, int r2=n-1) {
if(l1<=l2&&r2<=r1) {
if(f||r2*x[0]+x[1]<st[i][1]) {
app(i, x, l2, r2);
return;
} else if(l2*x[0]+x[1]>=st[i][0])
return;
}
int m2=(l2+r2)/2;
psh(i, l2, m2, r2);
if(l1<=m2)
upd(l1, r1, x, f, 2*i, l2, m2);
if(m2<r1)
upd(l1, r1, x, f, 2*i+1, m2+1, r2);
st[i]={st[2*i][0], st[2*i+1][1]};
}
ll qry(int l1, int i=1, int l2=0, int r2=n-1) {
if(l2==r2)
return st[i][0];
int m2=(l2+r2)/2;
psh(i, l2, m2, r2);
return l1<=m2?qry(l1, 2*i, l2, m2):qry(l1, 2*i+1, m2+1, r2);
}
int dfs(int l=0, int r=n-1) {
if(l>r)
return -1;
int u=abs(lca(l, r)[1]), lc=dfs(l, u-1), rc=dfs(u+1, r);
upd(u, u, {1, -u}, 1);
for(int i : ta[u]) {
//cout << u << " " << i << " " << ql[i] << " " << qr[i] << endl;
//cout << qry(qr[i])+(u-ql[i]+1ll)*a[0][u][0] << endl;
ans[i]=min(qry(qr[i])+(u-ql[i]+1ll)*a[0][u][0], ans[i]);
}
upd(u, r, {0, (u-l+1ll)*a[0][u][0]}, 1);
upd(u, r, {a[0][u][0], (~lc?qry(u-1):0)-(u-1ll)*a[0][u][0]}, 0);
//cout << "dbg " << u << endl;
//for(int i=l; i<=r; ++i)
//cout << i << " " << qry(i) << endl;
return u;
}
vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
n=h.size(), q=l.size();
for(int i=0; i<n; ++i)
a[0][i]={h[i], i};
for(int k=1; k<20; ++k)
for(int i=0; i<=n-(1<<k); ++i)
a[k][i]=max(a[k-1][i], a[k-1][i+(1<<k-1)]);
ql=l, qr=r;
ans=vector<ll>(q, 1e18);
for(int i=0; i<q; ++i) {
int w=lca(l[i], r[i])[1];
ta[w].push_back(i);
}
dfs();
reverse(ta, ta+n);
for(int i=0; i<q; ++i)
tie(ql[i], qr[i])=make_pair(n-1-qr[i], n-1-ql[i]);
for(int i=0; i<n; ++i)
a[0][i]={h[n-1-i], -i};
for(int k=1; k<20; ++k)
for(int i=0; i<=n-(1<<k); ++i)
a[k][i]=max(a[k-1][i], a[k-1][i+(1<<k-1)]);
dfs();
return ans;
}
Compilation message
meetings.cpp: In function 'int dfs(int, int)':
meetings.cpp:63:43: warning: unused variable 'rc' [-Wunused-variable]
int u=abs(lca(l, r)[1]), lc=dfs(l, u-1), rc=dfs(u+1, r);
^~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:84:41: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
a[k][i]=max(a[k-1][i], a[k-1][i+(1<<k-1)]);
~^~
meetings.cpp:99:41: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
a[k][i]=max(a[k-1][i], a[k-1][i+(1<<k-1)]);
~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
17912 KB |
Output is correct |
2 |
Correct |
26 ms |
18616 KB |
Output is correct |
3 |
Correct |
25 ms |
18612 KB |
Output is correct |
4 |
Correct |
25 ms |
18524 KB |
Output is correct |
5 |
Correct |
26 ms |
18524 KB |
Output is correct |
6 |
Correct |
25 ms |
18680 KB |
Output is correct |
7 |
Correct |
25 ms |
18608 KB |
Output is correct |
8 |
Correct |
25 ms |
18828 KB |
Output is correct |
9 |
Correct |
26 ms |
18652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
17912 KB |
Output is correct |
2 |
Correct |
26 ms |
18616 KB |
Output is correct |
3 |
Correct |
25 ms |
18612 KB |
Output is correct |
4 |
Correct |
25 ms |
18524 KB |
Output is correct |
5 |
Correct |
26 ms |
18524 KB |
Output is correct |
6 |
Correct |
25 ms |
18680 KB |
Output is correct |
7 |
Correct |
25 ms |
18608 KB |
Output is correct |
8 |
Correct |
25 ms |
18828 KB |
Output is correct |
9 |
Correct |
26 ms |
18652 KB |
Output is correct |
10 |
Correct |
35 ms |
19372 KB |
Output is correct |
11 |
Correct |
35 ms |
19296 KB |
Output is correct |
12 |
Correct |
36 ms |
19308 KB |
Output is correct |
13 |
Correct |
34 ms |
19292 KB |
Output is correct |
14 |
Correct |
34 ms |
19576 KB |
Output is correct |
15 |
Correct |
35 ms |
19292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
17944 KB |
Output is correct |
2 |
Correct |
83 ms |
22256 KB |
Output is correct |
3 |
Correct |
459 ms |
50012 KB |
Output is correct |
4 |
Correct |
429 ms |
44040 KB |
Output is correct |
5 |
Correct |
473 ms |
51844 KB |
Output is correct |
6 |
Correct |
471 ms |
52188 KB |
Output is correct |
7 |
Correct |
469 ms |
53036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
17944 KB |
Output is correct |
2 |
Correct |
83 ms |
22256 KB |
Output is correct |
3 |
Correct |
459 ms |
50012 KB |
Output is correct |
4 |
Correct |
429 ms |
44040 KB |
Output is correct |
5 |
Correct |
473 ms |
51844 KB |
Output is correct |
6 |
Correct |
471 ms |
52188 KB |
Output is correct |
7 |
Correct |
469 ms |
53036 KB |
Output is correct |
8 |
Correct |
445 ms |
44552 KB |
Output is correct |
9 |
Correct |
394 ms |
44480 KB |
Output is correct |
10 |
Correct |
426 ms |
44536 KB |
Output is correct |
11 |
Correct |
424 ms |
43936 KB |
Output is correct |
12 |
Correct |
395 ms |
43864 KB |
Output is correct |
13 |
Correct |
418 ms |
44024 KB |
Output is correct |
14 |
Correct |
458 ms |
50008 KB |
Output is correct |
15 |
Correct |
419 ms |
43848 KB |
Output is correct |
16 |
Correct |
492 ms |
50264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
17912 KB |
Output is correct |
2 |
Correct |
26 ms |
18616 KB |
Output is correct |
3 |
Correct |
25 ms |
18612 KB |
Output is correct |
4 |
Correct |
25 ms |
18524 KB |
Output is correct |
5 |
Correct |
26 ms |
18524 KB |
Output is correct |
6 |
Correct |
25 ms |
18680 KB |
Output is correct |
7 |
Correct |
25 ms |
18608 KB |
Output is correct |
8 |
Correct |
25 ms |
18828 KB |
Output is correct |
9 |
Correct |
26 ms |
18652 KB |
Output is correct |
10 |
Correct |
35 ms |
19372 KB |
Output is correct |
11 |
Correct |
35 ms |
19296 KB |
Output is correct |
12 |
Correct |
36 ms |
19308 KB |
Output is correct |
13 |
Correct |
34 ms |
19292 KB |
Output is correct |
14 |
Correct |
34 ms |
19576 KB |
Output is correct |
15 |
Correct |
35 ms |
19292 KB |
Output is correct |
16 |
Correct |
18 ms |
17944 KB |
Output is correct |
17 |
Correct |
83 ms |
22256 KB |
Output is correct |
18 |
Correct |
459 ms |
50012 KB |
Output is correct |
19 |
Correct |
429 ms |
44040 KB |
Output is correct |
20 |
Correct |
473 ms |
51844 KB |
Output is correct |
21 |
Correct |
471 ms |
52188 KB |
Output is correct |
22 |
Correct |
469 ms |
53036 KB |
Output is correct |
23 |
Correct |
445 ms |
44552 KB |
Output is correct |
24 |
Correct |
394 ms |
44480 KB |
Output is correct |
25 |
Correct |
426 ms |
44536 KB |
Output is correct |
26 |
Correct |
424 ms |
43936 KB |
Output is correct |
27 |
Correct |
395 ms |
43864 KB |
Output is correct |
28 |
Correct |
418 ms |
44024 KB |
Output is correct |
29 |
Correct |
458 ms |
50008 KB |
Output is correct |
30 |
Correct |
419 ms |
43848 KB |
Output is correct |
31 |
Correct |
492 ms |
50264 KB |
Output is correct |
32 |
Correct |
3802 ms |
234424 KB |
Output is correct |
33 |
Correct |
3336 ms |
234364 KB |
Output is correct |
34 |
Correct |
3647 ms |
234356 KB |
Output is correct |
35 |
Correct |
3839 ms |
235808 KB |
Output is correct |
36 |
Correct |
3325 ms |
235036 KB |
Output is correct |
37 |
Correct |
3582 ms |
234572 KB |
Output is correct |
38 |
Correct |
4191 ms |
281692 KB |
Output is correct |
39 |
Correct |
4480 ms |
281704 KB |
Output is correct |
40 |
Correct |
4067 ms |
240820 KB |
Output is correct |
41 |
Correct |
4755 ms |
323088 KB |
Output is correct |
42 |
Correct |
4894 ms |
326364 KB |
Output is correct |
43 |
Correct |
4894 ms |
326368 KB |
Output is correct |
44 |
Correct |
4589 ms |
281400 KB |
Output is correct |