This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include"meetings.h"
#define N 750009
#define LG 20
#define lc(i) ((i)<<1|1)
#define rc(i) ((i)+1<<1)
#define int long long
using namespace std;
int n,q,a[N],lg[N],st[LG][N],trek[N<<2],treb[N<<2],lazy[N<<2];
int lft[N<<2],rgt[N<<2];
vector<int>ql[N],qr[N],id[N],ans;
inline int qmx(const int&l,const int&r)
{
int i=lg[r-l];
if(a[st[i][l]]>a[st[i][r-(1<<i)+1]])return st[i][l];
else return st[i][r-(1<<i)+1];
}
inline void pd(const int&i,const int&l,const int&r)
{
if(trek[i]^1<<30)
{
int mid=l+r>>1;
trek[lc(i)]=trek[rc(i)]=trek[i];
treb[lc(i)]=treb[rc(i)]=treb[i];
lazy[lc(i)]=lazy[rc(i)]=0;
lft[lc(i)]=trek[i]*l+treb[i];
rgt[lc(i)]=trek[i]*mid+treb[i];
lft[rc(i)]=trek[i]*(mid+1)+treb[i];
rgt[rc(i)]=trek[i]*r+treb[i];
trek[i]=1<<30;
}
if(lazy[i])
{
lazy[lc(i)]+=lazy[i];
lazy[rc(i)]+=lazy[i];
lft[lc(i)]+=lazy[i];
rgt[lc(i)]+=lazy[i];
lft[rc(i)]+=lazy[i];
rgt[rc(i)]+=lazy[i];
lazy[i]=0;
}
}
inline void push(const int&i,const int&l,const int&r,const int&ql,
const int&qr,const int&k,const int&b)
{
if(qr<l||r<ql)return;
if(ql<=l&&r<=qr)
{
trek[i]=k;treb[i]=b;lazy[i]=0;
lft[i]=k*l+b;
rgt[i]=k*r+b;
return;
}
int mid=l+r>>1;pd(i,l,r);
push(lc(i),l,mid,ql,qr,k,b);
push(rc(i),mid+1,r,ql,qr,k,b);
lft[i]=lft[lc(i)];rgt[i]=rgt[rc(i)];
}
inline int qry(const int&i,const int&l,const int&r,const int&p)
{
if(l==r)return lft[i];
int mid=l+r>>1;pd(i,l,r);
if(p<=mid)return qry(lc(i),l,mid,p);
return qry(rc(i),mid+1,r,p);
}
inline void add(const int&i,const int&l,const int&r,const int&ql,
const int&qr,const int&x)
{
if(qr<l||r<ql)return;
if(ql<=l&&r<=qr){lazy[i]+=x;lft[i]+=x;rgt[i]+=x;return;}
int mid=l+r>>1;pd(i,l,r);
add(lc(i),l,mid,ql,qr,x);add(rc(i),mid+1,r,ql,qr,x);
lft[i]=lft[lc(i)];rgt[i]=rgt[rc(i)];
}
inline int find(const int&i,const int&l,const int&r,const int&ql,
const int&qr,const int&k,const int&b,const bool&dir)
{
if(qr<l||r<ql)return-1;
if(!dir)
{
if(qr>=r&&rgt[i]<=k*r+b)return-1;
if(ql<=l&&lft[i]>k*l+b)return l;
int mid=l+r>>1;pd(i,l,r);
int tmp=find(lc(i),l,mid,ql,qr,k,b,0);
if(~tmp)return tmp;
return find(rc(i),mid+1,r,ql,qr,k,b,0);
}
else
{
if(ql<=l&&lft[i]<=k*l+b)return-1;
if(qr>=r&&rgt[i]>k*r+b)return r;
int mid=l+r>>1;pd(i,l,r);
int tmp=find(rc(i),mid+1,r,ql,qr,k,b,1);
if(~tmp)return tmp;
return find(lc(i),l,mid,ql,qr,k,b,1);
}
}
inline void dfs1(const int&l,const int&r)
{
if(l==r){push(0,0,n-1,l,l,0,a[l]);return;}
int i=qmx(l,r);
if(i==l)
{
dfs1(i+1,r);
push(0,0,n-1,i,i,0,qry(0,0,n-1,i+1)+a[i]);
for(int j=0;j<ql[i].size();++j)
ans[id[i][j]]=min(ans[id[i][j]],a[i]*(qr[i][j]-i+1));
return;
}
if(i==r)
{
dfs1(l,i-1);
push(0,0,n-1,i,i,0,0);
for(int j=0;j<ql[i].size();++j)
ans[id[i][j]]=min(ans[id[i][j]],qry(0,0,n-1,ql[i][j])+a[i]);
add(0,0,n-1,l,i,a[i]);
return;
}
dfs1(l,i-1);dfs1(i+1,r);
push(0,0,n-1,i,i,0,0);
for(int j=0;j<ql[i].size();++j)
ans[id[i][j]]=min(ans[id[i][j]],
qry(0,0,n-1,ql[i][j])+a[i]*(qr[i][j]-i+1));
push(0,0,n-1,i,i,0,qry(0,0,n-1,i+1)+a[i]);
add(0,0,n-1,l,i-1,a[i]*(r-i+1));
int k=-a[i],b=qry(0,0,n-1,i)+a[i]*i;
int x=find(0,0,n-1,l,i-1,k,b,0);
if(~x)push(0,0,n-1,x,i-1,k,b);
}
inline void dfs2(const int&l,const int&r)
{
if(l==r){push(0,0,n-1,l,l,0,a[l]);return;}
int i=qmx(l,r);
if(i==l)
{
dfs2(i+1,r);
push(0,0,n-1,i,i,0,0);
for(int j=0;j<ql[i].size();++j)
ans[id[i][j]]=min(ans[id[i][j]],qry(0,0,n-1,qr[i][j])+a[i]);
add(0,0,n-1,i,r,a[i]);
return;
}
if(i==r)
{
dfs2(l,i-1);
push(0,0,n-1,i,i,0,qry(0,0,n-1,i-1)+a[i]);
for(int j=0;j<ql[i].size();++j)
ans[id[i][j]]=min(ans[id[i][j]],a[i]*(i-ql[i][j]+1));
return;
}
dfs2(l,i-1);dfs2(i+1,r);
push(0,0,n-1,i,i,0,0);
for(int j=0;j<ql[i].size();++j)
ans[id[i][j]]=min(ans[id[i][j]],
qry(0,0,n-1,qr[i][j])+a[i]*(i-ql[i][j]+1));
push(0,0,n-1,i,i,0,qry(0,0,n-1,i-1)+a[i]);
add(0,0,n-1,i+1,r,a[i]*(i-l+1));
int k=a[i],b=qry(0,0,n-1,i)-a[i]*i;
int x=find(0,0,n-1,i+1,r,k,b,1);
if(~x)push(0,0,n-1,i+1,x,k,b);
}
vector<int>minimum_costs(vector<signed>H,vector<signed>L,vector<signed>R)
{
n=H.size();q=L.size();ans.resize(q);
for(int i=0;i<n;a[i]=H[i],++i);
for(int i=2;i<n;lg[i]=lg[i>>1]+1,++i);
for(int i=n-1;i>=0;--i)
{
st[0][i]=i;
for(int j=1;j<LG;++j)
if(i+(1<<j-1)<n)
if(a[st[j-1][i]]>a[st[j-1][i+(1<<j-1)]])
st[j][i]=st[j-1][i];
else st[j][i]=st[j-1][i+(1<<j-1)];
else st[j][i]=st[j-1][i];
}
for(int i=0,u,v,w;i<q;++i)
{
u=L[i],v=R[i],w=qmx(u,v);
if(u==v){ans[i]=a[u];continue;}
ql[w].emplace_back(u),qr[w].emplace_back(v),
id[w].emplace_back(i);ans[i]=1ll<<60;
}
for(int i=0;i<N<<2;trek[i++]=1<<30);
dfs1(0,n-1);
for(int i=0;i<N<<2;trek[i++]=1<<30);
dfs2(0,n-1);
return ans;
}
Compilation message (stderr)
meetings.cpp: In function 'void pd(const long long int&, const long long int&, const long long int&)':
meetings.cpp:21:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
21 | int mid=l+r>>1;
| ~^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
5 | #define rc(i) ((i)+1<<1)
| ~~~^~
meetings.cpp:22:20: note: in expansion of macro 'rc'
22 | trek[lc(i)]=trek[rc(i)]=trek[i];
| ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
5 | #define rc(i) ((i)+1<<1)
| ~~~^~
meetings.cpp:23:20: note: in expansion of macro 'rc'
23 | treb[lc(i)]=treb[rc(i)]=treb[i];
| ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
5 | #define rc(i) ((i)+1<<1)
| ~~~^~
meetings.cpp:24:20: note: in expansion of macro 'rc'
24 | lazy[lc(i)]=lazy[rc(i)]=0;
| ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
5 | #define rc(i) ((i)+1<<1)
| ~~~^~
meetings.cpp:27:7: note: in expansion of macro 'rc'
27 | lft[rc(i)]=trek[i]*(mid+1)+treb[i];
| ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
5 | #define rc(i) ((i)+1<<1)
| ~~~^~
meetings.cpp:28:7: note: in expansion of macro 'rc'
28 | rgt[rc(i)]=trek[i]*r+treb[i];
| ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
5 | #define rc(i) ((i)+1<<1)
| ~~~^~
meetings.cpp:34:8: note: in expansion of macro 'rc'
34 | lazy[rc(i)]+=lazy[i];
| ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
5 | #define rc(i) ((i)+1<<1)
| ~~~^~
meetings.cpp:37:7: note: in expansion of macro 'rc'
37 | lft[rc(i)]+=lazy[i];
| ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
5 | #define rc(i) ((i)+1<<1)
| ~~~^~
meetings.cpp:38:7: note: in expansion of macro 'rc'
38 | rgt[rc(i)]+=lazy[i];
| ^~
meetings.cpp: In function 'void push(const long long int&, const long long int&, const long long int&, const long long int&, const long long int&, const long long int&, const long long int&)':
meetings.cpp:53:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | int mid=l+r>>1;pd(i,l,r);
| ~^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
5 | #define rc(i) ((i)+1<<1)
| ~~~^~
meetings.cpp:55:7: note: in expansion of macro 'rc'
55 | push(rc(i),mid+1,r,ql,qr,k,b);
| ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
5 | #define rc(i) ((i)+1<<1)
| ~~~^~
meetings.cpp:56:31: note: in expansion of macro 'rc'
56 | lft[i]=lft[lc(i)];rgt[i]=rgt[rc(i)];
| ^~
meetings.cpp: In function 'long long int qry(const long long int&, const long long int&, const long long int&, const long long int&)':
meetings.cpp:61:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int mid=l+r>>1;pd(i,l,r);
| ~^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
5 | #define rc(i) ((i)+1<<1)
| ~~~^~
meetings.cpp:63:13: note: in expansion of macro 'rc'
63 | return qry(rc(i),mid+1,r,p);
| ^~
meetings.cpp: In function 'void add(const long long int&, const long long int&, const long long int&, const long long int&, const long long int&, const long long int&)':
meetings.cpp:70:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
70 | int mid=l+r>>1;pd(i,l,r);
| ~^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
5 | #define rc(i) ((i)+1<<1)
| ~~~^~
meetings.cpp:71:31: note: in expansion of macro 'rc'
71 | add(lc(i),l,mid,ql,qr,x);add(rc(i),mid+1,r,ql,qr,x);
| ^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
5 | #define rc(i) ((i)+1<<1)
| ~~~^~
meetings.cpp:72:31: note: in expansion of macro 'rc'
72 | lft[i]=lft[lc(i)];rgt[i]=rgt[rc(i)];
| ^~
meetings.cpp: In function 'long long int find(const long long int&, const long long int&, const long long int&, const long long int&, const long long int&, const long long int&, const long long int&, const bool&)':
meetings.cpp:82:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
82 | int mid=l+r>>1;pd(i,l,r);
| ~^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
5 | #define rc(i) ((i)+1<<1)
| ~~~^~
meetings.cpp:85:15: note: in expansion of macro 'rc'
85 | return find(rc(i),mid+1,r,ql,qr,k,b,0);
| ^~
meetings.cpp:91:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
91 | int mid=l+r>>1;pd(i,l,r);
| ~^~
meetings.cpp:5:19: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
5 | #define rc(i) ((i)+1<<1)
| ~~~^~
meetings.cpp:92:16: note: in expansion of macro 'rc'
92 | int tmp=find(rc(i),mid+1,r,ql,qr,k,b,1);
| ^~
meetings.cpp: In function 'void dfs1(const long long int&, const long long int&)':
meetings.cpp:105:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int j=0;j<ql[i].size();++j)
| ~^~~~~~~~~~~~~
meetings.cpp:113:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int j=0;j<ql[i].size();++j)
| ~^~~~~~~~~~~~~
meetings.cpp:120:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
120 | for(int j=0;j<ql[i].size();++j)
| ~^~~~~~~~~~~~~
meetings.cpp: In function 'void dfs2(const long long int&, const long long int&)':
meetings.cpp:137:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for(int j=0;j<ql[i].size();++j)
| ~^~~~~~~~~~~~~
meetings.cpp:146:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
146 | for(int j=0;j<ql[i].size();++j)
| ~^~~~~~~~~~~~~
meetings.cpp:152:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | for(int j=0;j<ql[i].size();++j)
| ~^~~~~~~~~~~~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:170:14: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
170 | if(i+(1<<j-1)<n)
| ~^~
meetings.cpp:171:39: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
171 | if(a[st[j-1][i]]>a[st[j-1][i+(1<<j-1)]])
| ~^~
meetings.cpp:173:34: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
173 | else st[j][i]=st[j-1][i+(1<<j-1)];
| ~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |