#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])
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);
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:78:41: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
a[k][i]=max(a[k-1][i], a[k-1][i+(1<<k-1)]);
~^~
meetings.cpp:93: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 |
25 ms |
18612 KB |
Output is correct |
3 |
Correct |
25 ms |
18524 KB |
Output is correct |
4 |
Correct |
25 ms |
18524 KB |
Output is correct |
5 |
Correct |
25 ms |
18552 KB |
Output is correct |
6 |
Correct |
25 ms |
18656 KB |
Output is correct |
7 |
Correct |
25 ms |
18616 KB |
Output is correct |
8 |
Correct |
25 ms |
18780 KB |
Output is correct |
9 |
Correct |
25 ms |
18652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
17912 KB |
Output is correct |
2 |
Correct |
25 ms |
18612 KB |
Output is correct |
3 |
Correct |
25 ms |
18524 KB |
Output is correct |
4 |
Correct |
25 ms |
18524 KB |
Output is correct |
5 |
Correct |
25 ms |
18552 KB |
Output is correct |
6 |
Correct |
25 ms |
18656 KB |
Output is correct |
7 |
Correct |
25 ms |
18616 KB |
Output is correct |
8 |
Correct |
25 ms |
18780 KB |
Output is correct |
9 |
Correct |
25 ms |
18652 KB |
Output is correct |
10 |
Correct |
35 ms |
19352 KB |
Output is correct |
11 |
Correct |
36 ms |
19340 KB |
Output is correct |
12 |
Correct |
35 ms |
19280 KB |
Output is correct |
13 |
Correct |
35 ms |
19320 KB |
Output is correct |
14 |
Correct |
36 ms |
19592 KB |
Output is correct |
15 |
Correct |
34 ms |
19320 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
17884 KB |
Output is correct |
2 |
Correct |
83 ms |
22152 KB |
Output is correct |
3 |
Correct |
459 ms |
49984 KB |
Output is correct |
4 |
Correct |
428 ms |
43996 KB |
Output is correct |
5 |
Correct |
476 ms |
51928 KB |
Output is correct |
6 |
Correct |
494 ms |
52192 KB |
Output is correct |
7 |
Correct |
484 ms |
53048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
17884 KB |
Output is correct |
2 |
Correct |
83 ms |
22152 KB |
Output is correct |
3 |
Correct |
459 ms |
49984 KB |
Output is correct |
4 |
Correct |
428 ms |
43996 KB |
Output is correct |
5 |
Correct |
476 ms |
51928 KB |
Output is correct |
6 |
Correct |
494 ms |
52192 KB |
Output is correct |
7 |
Correct |
484 ms |
53048 KB |
Output is correct |
8 |
Correct |
447 ms |
44548 KB |
Output is correct |
9 |
Correct |
412 ms |
44492 KB |
Output is correct |
10 |
Correct |
429 ms |
44536 KB |
Output is correct |
11 |
Correct |
421 ms |
43936 KB |
Output is correct |
12 |
Correct |
391 ms |
43820 KB |
Output is correct |
13 |
Correct |
418 ms |
44028 KB |
Output is correct |
14 |
Correct |
471 ms |
50080 KB |
Output is correct |
15 |
Correct |
418 ms |
43856 KB |
Output is correct |
16 |
Correct |
483 ms |
50232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
17912 KB |
Output is correct |
2 |
Correct |
25 ms |
18612 KB |
Output is correct |
3 |
Correct |
25 ms |
18524 KB |
Output is correct |
4 |
Correct |
25 ms |
18524 KB |
Output is correct |
5 |
Correct |
25 ms |
18552 KB |
Output is correct |
6 |
Correct |
25 ms |
18656 KB |
Output is correct |
7 |
Correct |
25 ms |
18616 KB |
Output is correct |
8 |
Correct |
25 ms |
18780 KB |
Output is correct |
9 |
Correct |
25 ms |
18652 KB |
Output is correct |
10 |
Correct |
35 ms |
19352 KB |
Output is correct |
11 |
Correct |
36 ms |
19340 KB |
Output is correct |
12 |
Correct |
35 ms |
19280 KB |
Output is correct |
13 |
Correct |
35 ms |
19320 KB |
Output is correct |
14 |
Correct |
36 ms |
19592 KB |
Output is correct |
15 |
Correct |
34 ms |
19320 KB |
Output is correct |
16 |
Correct |
18 ms |
17884 KB |
Output is correct |
17 |
Correct |
83 ms |
22152 KB |
Output is correct |
18 |
Correct |
459 ms |
49984 KB |
Output is correct |
19 |
Correct |
428 ms |
43996 KB |
Output is correct |
20 |
Correct |
476 ms |
51928 KB |
Output is correct |
21 |
Correct |
494 ms |
52192 KB |
Output is correct |
22 |
Correct |
484 ms |
53048 KB |
Output is correct |
23 |
Correct |
447 ms |
44548 KB |
Output is correct |
24 |
Correct |
412 ms |
44492 KB |
Output is correct |
25 |
Correct |
429 ms |
44536 KB |
Output is correct |
26 |
Correct |
421 ms |
43936 KB |
Output is correct |
27 |
Correct |
391 ms |
43820 KB |
Output is correct |
28 |
Correct |
418 ms |
44028 KB |
Output is correct |
29 |
Correct |
471 ms |
50080 KB |
Output is correct |
30 |
Correct |
418 ms |
43856 KB |
Output is correct |
31 |
Correct |
483 ms |
50232 KB |
Output is correct |
32 |
Correct |
3780 ms |
234444 KB |
Output is correct |
33 |
Correct |
3315 ms |
234372 KB |
Output is correct |
34 |
Correct |
3588 ms |
234296 KB |
Output is correct |
35 |
Correct |
3800 ms |
235748 KB |
Output is correct |
36 |
Correct |
3318 ms |
235072 KB |
Output is correct |
37 |
Correct |
3584 ms |
234520 KB |
Output is correct |
38 |
Correct |
4157 ms |
281684 KB |
Output is correct |
39 |
Correct |
4356 ms |
281760 KB |
Output is correct |
40 |
Correct |
3966 ms |
240872 KB |
Output is correct |
41 |
Correct |
4731 ms |
323140 KB |
Output is correct |
42 |
Correct |
4867 ms |
326352 KB |
Output is correct |
43 |
Correct |
4941 ms |
326292 KB |
Output is correct |
44 |
Correct |
4614 ms |
281368 KB |
Output is correct |