#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));
#define maxn 200005
int n,q,a[maxn],b[maxn],s,t,u,r[maxn];
ll x[maxn],ans[maxn];
vi disc;
stack<int> st;
int get(int i){
return upper_bound(all(disc),i)-disc.begin();
}
struct query{
int u,i,mult;
};
vector<query> qrys[maxn];
struct maxseg{
int s,e,m,v;maxseg *l,*r;
maxseg(int _s,int _e){
s=_s;e=_e;m=(s+e)>>1;v=0;
if(s!=e)l=new maxseg(s,m),r=new maxseg(m+1,e);
}
void up(int x,int nv){
if(s==x&&e==x){ v=nv;return; }
if(x<=m)l->up(x,nv);
else r->up(x,nv);
v=max(l->v,r->v);
}
int qry(int x,int y){
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
if(x>m)return r->qry(x,y);
return max(l->qry(x,m),r->qry(m+1,y));
}
}*die;
struct minseg{
int s,e,m;ii v;minseg *l,*r;
minseg(int _s,int _e){
s=_s;e=_e;m=(s+e)>>1;v={0,0};
if(s!=e)l=new minseg(s,m),r=new minseg(m+1,e);
}
void up(int x,ii nv){
if(s==x&&e==x){ v=nv;return; }
if(x<=m)l->up(x,nv);
else r->up(x,nv);
v=min(l->v,r->v);
}
ii qry(int x,int y){
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
if(x>m)return r->qry(x,y);
return min(l->qry(x,m),r->qry(m+1,y));
}
}*getmin;
struct fw{
ll ft[maxn];
void init(){
for(int i=1;i<=n+1;++i){
ft[i]=0;
}
}
void up(int x,int y,ll v){
while(x<=n+1){
ft[x]+=v;x+=x&-x;
}
++y;
while(y<=n+1){
ft[y]-=v;y+=y&-y;
}
}
ll qry(int x){
ll res=0;
while(x){
res+=ft[x];x-=x&-x;
}
return res;
}
}*m=new fw(),*c=new fw();
int main(){
sf("%d%d",&n,&q);
die=new maxseg(1,n+1);
getmin=new minseg(1,n+1);
for(int i=1;i<=n;++i){
sf("%d",&a[i]);
die->up(i+1,a[i]);//max jump
x[i+1]=x[i]+a[i];
}
for(int i=1;i<=n;++i){
sf("%d",&b[i]);
getmin->up(i,{b[i],i});
}
for(int i=0;i<q;++i){
sf("%d%d%d",&s,&t,&u);
if(die->qry(s+1,t)>u){
//max distance is more than u, impossible
ans[i]=-1;
}
else{
qrys[s].pb({u,i,1});
//answer is cost from s to n+1 - cost from minpos to n+1 +
//cost to get from minpos to t, buying from minpos
int leftpos=max(s,lower_bound(x+1,x+n+1,x[t]-u)-x);
dbg("leftpos: %lld %d\n",x[t]-u,leftpos);
int minpos=getmin->qry(leftpos,t-1).se;
ans[i]=(x[t]-x[minpos])*b[minpos];
qrys[minpos].pb({u,i,-1});
dbg("%d: %d %d %d\n",s,u,i,1);
dbg("%d: %d %d %d\n",minpos,u,i,-1);
disc.pb(u);
}
}
disc.pb(INF);
sort(all(disc));
disc.erase(unique(all(disc)),disc.end());
m->init();c->init();
b[n+1]=-INF;st.push(n+1);
for(int i=n;i>=1;--i){
while(b[st.top()]>=b[i]){
int j=st.top();st.pop();
int dl=get(x[j]-x[i]);
int dr=get(x[r[j]]-x[i]);
m->up(dl+1,dr,-b[j]);
c->up(dl+1,dr,(x[j]-x[i])*b[j]);
c->up(dr+1,maxn-1,-(x[r[j]]-x[j])*b[j]);
}
r[i]=st.top();
int d=get(x[r[i]]-x[i]);
m->up(1,d,b[i]);//x<d:y=b[i]*x
c->up(d+1,maxn-1,(x[r[i]]-x[i])*b[i]);//x>=d:y=d*b[i]
st.push(i);
for(query q:qrys[i]){
ans[q.i]+=q.mult*(q.u*m->qry(get(q.u))+c->qry(get(q.u)));
dbg("%d %d %d %d: %lld\n",i,q.u,q.i,q.mult,q.mult*(q.u*m->qry(get(q.u))+c->qry(get(q.u))));
}
}
for(int i=0;i<q;++i){
pf("%lld\n",ans[i]);
}
}
/*
5 4
3 4 1 1 4
2 5 1 2 1
1 6 3
1 6 4
3 5 1
2 5 9
*/
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:140:53: error: no matching function for call to 'max(int&, long int)'
140 | int leftpos=max(s,lower_bound(x+1,x+n+1,x[t]-u)-x);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: template argument deduction/substitution failed:
Main.cpp:140:53: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long int')
140 | int leftpos=max(s,lower_bound(x+1,x+n+1,x[t]-u)-x);
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
Main.cpp:140:53: note: deduced conflicting types for parameter 'const _Tp' ('int' and 'long int')
140 | int leftpos=max(s,lower_bound(x+1,x+n+1,x[t]-u)-x);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
Main.cpp:140:53: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
140 | int leftpos=max(s,lower_bound(x+1,x+n+1,x[t]-u)-x);
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
Main.cpp:140:53: note: mismatched types 'std::initializer_list<_Tp>' and 'int'
140 | int leftpos=max(s,lower_bound(x+1,x+n+1,x[t]-u)-x);
| ^
Main.cpp:114:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | sf("%d%d",&n,&q);
| ^
Main.cpp:120:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
120 | sf("%d",&a[i]);
| ^
Main.cpp:125:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
125 | sf("%d",&b[i]);
| ^
Main.cpp:130:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
130 | sf("%d%d%d",&s,&t,&u);
| ^
