#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
const int N=750050;
const int M=2*N;
const ll inf=1e18;
int n,q;
int l[N],r[N],h[N];
ll ans[N];
struct LiChaoSegmentTree
{
struct Line
{
ll k,n;
Line(){ k=n=0;}
Line(ll a, ll b):k(a),n(b){}
ll Get(ll x){ return k*x+n;}
} line[M];
int ls[M],rs[M],tsz,root;
ll lzy[M];
LiChaoSegmentTree(){}
void Build(int &c, int ss, int se)
{
c=++tsz;lzy[c]=0;line[c]=Line(0,inf);
if(ss==se){ line[c]=Line();return;}
int mid=ss+se>>1;
Build(ls[c],ss,mid);
Build(rs[c],mid+1,se);
}
void Build(){ Build(root,1,n);}
void upd(int c, ll f)
{
line[c].n+=f;
lzy[c]+=f;
}
void push(int c)
{
if(lzy[c])
{
upd(ls[c],lzy[c]);
upd(rs[c],lzy[c]);
lzy[c]=0;
}
}
void Add(int c, int ss, int se, int qs, int qe, ll f)
{
if(qs>qe || qs>se || ss>qe) return;
if(qs<=ss && qe>=se){ upd(c,f);return;}
push(c);
int mid=ss+se>>1;
Add(ls[c],ss,mid,qs,qe,f);
Add(rs[c],mid+1,se,qs,qe,f);
}
void Add(int l, int r, ll f){ Add(root,1,n,l,r,f);}
void Set(int c, int ss, int se, int qs, int qe, Line k)
{
if(qs>qe || qs>se || ss>qe) return;
if(qs<=ss && qe>=se)
{
ll A=k.Get(ss),B=line[c].Get(ss),C=k.Get(se),D=line[c].Get(se);
if(A<=B && C<=D){ line[c]=k;return;}
if(A>=B && C>=D) return;
push(c);
int mid=ss+se>>1;
if(A<=B) swap(line[c],k);
if(line[c].Get(mid)<=k.Get(mid)) Set(rs[c],mid+1,se,qs,qe,k);
else swap(line[c],k),Set(ls[c],ss,mid,qs,qe,k);
return;
}
push(c);
int mid=ss+se>>1;
Set(ls[c],ss,mid,qs,qe,k);
Set(rs[c],mid+1,se,qs,qe,k);
}
void Set(int l, int r, ll b, ll a){ Set(root,1,n,l,r,Line(a,b));}
ll Get(int c, int ss, int se, int qi)
{
ll ans=line[c].Get(qi);
if(ss==se) return ans;
push(c);
int mid=ss+se>>1;
if(qi<=mid) return min(ans,Get(ls[c],ss,mid,qi));
else return min(ans,Get(rs[c],mid+1,se,qi));
}
ll Get(int qi){ return Get(root,1,n,qi);}
} FW,BW;
struct SegmentTree
{
int mx[M];
void init(){ for(int i=1;i<M;i++) mx[i]=0;}
int my_max(int x, int y){ return mp(h[x],x)>mp(h[y],y)?x:y;}
void Build()
{
for(int i=n+N;i>=N;i--) mx[i]=i-N;
for(int i=N-1;i;i--) mx[i]=my_max(mx[i<<1],mx[i<<1|1]);
}
int Get(int l, int r)
{
int ans=0;
for(l+=N,r+=N;l<=r;l>>=1,r>>=1)
{
if(l%2==1) ans=my_max(ans,mx[l++]);
if(r%2==0) ans=my_max(ans,mx[r--]);
}
return ans;
}
} RMQ;
vector<int> Qs[N];
void Solve(int l, int r)
{
if(l>r) return;
int m=RMQ.Get(l,r);
Solve(l,m-1);Solve(m+1,r);
for(int i:Qs[m]) ans[i]=min(FW.Get(::r[i])+(ll)h[m]*(m-::l[i]+1),BW.Get(::l[i])+(ll)h[m]*(::r[i]-m+1));
FW.Add(m,r,(ll)h[m]*(m-l+1));
if(m!=l) FW.Set(m,r,FW.Get(m-1)-(ll)h[m]*(m-1),h[m]);
BW.Add(l,m,(ll)h[m]*(r-m+1));
if(m!=r) BW.Set(l,m,BW.Get(m+1)+(ll)h[m]*(m+1),-h[m]);
}
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R)
{
n=H.size();q=L.size();
for(int i=1;i<=n;i++) h[i]=H[i-1];
for(int i=1;i<=q;i++) l[i]=L[i-1]+1,r[i]=R[i-1]+1;
RMQ.Build();
for(int i=1;i<=q;i++) Qs[RMQ.Get(l[i],r[i])].pb(i);
FW.Build();BW.Build();
Solve(1,n);
vector<ll> ret;
for(int i=1;i<=q;i++) ret.pb(ans[i]);
return ret;
}
Compilation message
meetings.cpp: In member function 'void LiChaoSegmentTree::Build(int&, int, int)':
meetings.cpp:29:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
meetings.cpp: In member function 'void LiChaoSegmentTree::Add(int, int, int, int, int, long long int)':
meetings.cpp:53:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
meetings.cpp: In member function 'void LiChaoSegmentTree::Set(int, int, int, int, int, LiChaoSegmentTree::Line)':
meetings.cpp:67:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
meetings.cpp:74:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
meetings.cpp: In member function 'long long int LiChaoSegmentTree::Get(int, int, int, int)':
meetings.cpp:84:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
67944 KB |
Output is correct |
2 |
Correct |
64 ms |
68072 KB |
Output is correct |
3 |
Correct |
63 ms |
68112 KB |
Output is correct |
4 |
Correct |
63 ms |
68200 KB |
Output is correct |
5 |
Correct |
63 ms |
68184 KB |
Output is correct |
6 |
Correct |
62 ms |
68464 KB |
Output is correct |
7 |
Correct |
62 ms |
68208 KB |
Output is correct |
8 |
Correct |
62 ms |
68504 KB |
Output is correct |
9 |
Correct |
63 ms |
68368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
67944 KB |
Output is correct |
2 |
Correct |
64 ms |
68072 KB |
Output is correct |
3 |
Correct |
63 ms |
68112 KB |
Output is correct |
4 |
Correct |
63 ms |
68200 KB |
Output is correct |
5 |
Correct |
63 ms |
68184 KB |
Output is correct |
6 |
Correct |
62 ms |
68464 KB |
Output is correct |
7 |
Correct |
62 ms |
68208 KB |
Output is correct |
8 |
Correct |
62 ms |
68504 KB |
Output is correct |
9 |
Correct |
63 ms |
68368 KB |
Output is correct |
10 |
Correct |
70 ms |
68704 KB |
Output is correct |
11 |
Correct |
67 ms |
68648 KB |
Output is correct |
12 |
Correct |
67 ms |
68660 KB |
Output is correct |
13 |
Correct |
67 ms |
68676 KB |
Output is correct |
14 |
Correct |
71 ms |
69132 KB |
Output is correct |
15 |
Correct |
69 ms |
68660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
67944 KB |
Output is correct |
2 |
Correct |
114 ms |
71780 KB |
Output is correct |
3 |
Correct |
327 ms |
89900 KB |
Output is correct |
4 |
Correct |
282 ms |
80900 KB |
Output is correct |
5 |
Correct |
272 ms |
91864 KB |
Output is correct |
6 |
Correct |
287 ms |
92484 KB |
Output is correct |
7 |
Correct |
346 ms |
94512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
67944 KB |
Output is correct |
2 |
Correct |
114 ms |
71780 KB |
Output is correct |
3 |
Correct |
327 ms |
89900 KB |
Output is correct |
4 |
Correct |
282 ms |
80900 KB |
Output is correct |
5 |
Correct |
272 ms |
91864 KB |
Output is correct |
6 |
Correct |
287 ms |
92484 KB |
Output is correct |
7 |
Correct |
346 ms |
94512 KB |
Output is correct |
8 |
Correct |
318 ms |
81632 KB |
Output is correct |
9 |
Correct |
228 ms |
81456 KB |
Output is correct |
10 |
Correct |
257 ms |
81644 KB |
Output is correct |
11 |
Correct |
296 ms |
80752 KB |
Output is correct |
12 |
Correct |
226 ms |
80588 KB |
Output is correct |
13 |
Correct |
251 ms |
80824 KB |
Output is correct |
14 |
Correct |
321 ms |
89968 KB |
Output is correct |
15 |
Correct |
278 ms |
80644 KB |
Output is correct |
16 |
Correct |
330 ms |
90348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
67944 KB |
Output is correct |
2 |
Correct |
64 ms |
68072 KB |
Output is correct |
3 |
Correct |
63 ms |
68112 KB |
Output is correct |
4 |
Correct |
63 ms |
68200 KB |
Output is correct |
5 |
Correct |
63 ms |
68184 KB |
Output is correct |
6 |
Correct |
62 ms |
68464 KB |
Output is correct |
7 |
Correct |
62 ms |
68208 KB |
Output is correct |
8 |
Correct |
62 ms |
68504 KB |
Output is correct |
9 |
Correct |
63 ms |
68368 KB |
Output is correct |
10 |
Correct |
70 ms |
68704 KB |
Output is correct |
11 |
Correct |
67 ms |
68648 KB |
Output is correct |
12 |
Correct |
67 ms |
68660 KB |
Output is correct |
13 |
Correct |
67 ms |
68676 KB |
Output is correct |
14 |
Correct |
71 ms |
69132 KB |
Output is correct |
15 |
Correct |
69 ms |
68660 KB |
Output is correct |
16 |
Correct |
61 ms |
67944 KB |
Output is correct |
17 |
Correct |
114 ms |
71780 KB |
Output is correct |
18 |
Correct |
327 ms |
89900 KB |
Output is correct |
19 |
Correct |
282 ms |
80900 KB |
Output is correct |
20 |
Correct |
272 ms |
91864 KB |
Output is correct |
21 |
Correct |
287 ms |
92484 KB |
Output is correct |
22 |
Correct |
346 ms |
94512 KB |
Output is correct |
23 |
Correct |
318 ms |
81632 KB |
Output is correct |
24 |
Correct |
228 ms |
81456 KB |
Output is correct |
25 |
Correct |
257 ms |
81644 KB |
Output is correct |
26 |
Correct |
296 ms |
80752 KB |
Output is correct |
27 |
Correct |
226 ms |
80588 KB |
Output is correct |
28 |
Correct |
251 ms |
80824 KB |
Output is correct |
29 |
Correct |
321 ms |
89968 KB |
Output is correct |
30 |
Correct |
278 ms |
80644 KB |
Output is correct |
31 |
Correct |
330 ms |
90348 KB |
Output is correct |
32 |
Correct |
2545 ms |
162484 KB |
Output is correct |
33 |
Correct |
1480 ms |
162172 KB |
Output is correct |
34 |
Correct |
1774 ms |
163648 KB |
Output is correct |
35 |
Correct |
2507 ms |
163860 KB |
Output is correct |
36 |
Correct |
1534 ms |
164528 KB |
Output is correct |
37 |
Correct |
1775 ms |
163980 KB |
Output is correct |
38 |
Correct |
2882 ms |
233136 KB |
Output is correct |
39 |
Correct |
2920 ms |
233140 KB |
Output is correct |
40 |
Correct |
2619 ms |
171160 KB |
Output is correct |
41 |
Correct |
2747 ms |
299804 KB |
Output is correct |
42 |
Correct |
3335 ms |
301240 KB |
Output is correct |
43 |
Correct |
3378 ms |
301108 KB |
Output is correct |
44 |
Correct |
3284 ms |
232880 KB |
Output is correct |