#include <bits/stdc++.h>
#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);
#ifdef NCGM
#include"debug.h"
#else
#define debug(...) "fr";
#endif
using namespace std;
const int N=1e5+3,B=320;
struct Query {
int s,t,u;
} q[N];
struct Node {
int len,s,t,s1,t1;
bool hasY;
ll x,y;
};
int n,m,r[N],f[N];
ll pf[N],a[N],b[N],ans[N];
stack<int> st;
vector<ll> big;
vector<int> suc[N],in[N*10];
vector<pair<int,int>> in1[N*10];
Node invl,d[N];
Node mrg(Node A, Node B) {
if (A.len==-1 || B.len==-1) return invl;
if (f[A.t]!=B.s) return invl;
Node ans;
ans.len=A.len+B.len;
ans.s=A.s,ans.t=B.t;
ans.hasY=A.hasY|B.hasY;
ans.s1=(A.s1==-1?B.s:A.s1);
ans.t1=(B.t1==-1?A.t:B.t1);
ans.x=A.x+B.x;
ans.y=A.y+B.y;
if (b[A.t]>=b[B.s]) {
if (A.len==1 || b[A.t1]>=b[A.t]) ans.x+=b[A.t]*(pf[B.s-1]-pf[A.t-1]);
else {
ans.y-=b[A.t];
ans.x+=b[A.t]*(pf[B.s-1]-pf[A.t1-1]);
}
// if (A.s==1 && A.t==2 && B.s==3 && B.t==3) debug(b[A.t1],b[A.t],ans.x,ans.y);
} else {
ans.hasY=1;
// if (A.t==1 && B.s==2 && B.t==2) debug(ans.x,ans.y);
if (A.len==1 || b[A.t1]>=b[A.t]) ans.y+=b[A.t];
else ans.x+=b[A.t]*(pf[A.t-1]-pf[A.t1-1]);
if (B.len>1) {
if (b[B.s]>=b[B.s1]) {
ans.y-=b[B.s];
ans.x+=b[B.s]*(pf[B.s1-1]-pf[A.t-1]);
ans.x-=b[B.s]*(pf[B.s1-1]-pf[B.s-1]);
} else {
ans.y-=b[B.s];
ans.x+=b[B.s]*(pf[B.s-1]-pf[A.t-1]);
}
}
}
return ans;
}
void recal(int x) {
ForD(i,min(n+1,(x+1)*B),x*B+1) {
d[i].len=1,d[i].s1=-1,d[i].t1=-1,d[i].s=d[i].t=i,d[i].x=d[i].y=0;
d[i].hasY=0;
}
ForD(i,min(n+1,(x+1)*B),x*B+1) {
if (f[i]>(x+1)*B || f[i]==-1) continue;
d[i]=mrg(d[i],d[f[i]]);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
invl.len=-1;
For(i,1,n) {
cin >> a[i];
pf[i]=pf[i-1]+a[i];
}
For(i,1,n) cin >> b[i];
fill(r+1,r+n+1,n+1);
r[n+1]=n+2;
f[n+1]=-1;
For(i,1,n) {
while(sz(st) && b[st.top()]>=b[i]) {
r[st.top()]=i;
st.pop();
}
st.push(i);
}
suc[n].pb(n+1);
ForD(i,n-1,1) {
int cur=i+1;
while(cur<n+1) {
// if (i==4) debug(cur,r[i]);
if (cur>n || r[i]<cur) break;
suc[i].pb(cur);
big.pb(pf[cur-1]-pf[i-1]);
cur=r[cur];
}
}
For(i,1,m) {
cin >> q[i].s >> q[i].t >> q[i].u;
big.pb(q[i].u);
}
sort(all(big));
unq(big);
For(i,1,n) {
for(auto el: suc[i]) {
int comp=(lower_bound(all(big),pf[el-1]-pf[i-1])-big.begin())+1;
in1[comp].pb({i,el});
}
}
For(i,1,m) {
int comp=(lower_bound(all(big),q[i].u)-big.begin())+1;
in[comp].pb(i);
}
For(i,1,n) {
f[i]=-1;
d[i].len=1,d[i].s1=-1,d[i].t1=-1,d[i].s=d[i].t=i,d[i].x=d[i].y=0;
d[i].hasY=0;
}
For(i,0,(n-1)/B) recal(i);
For(i,1,sz(big)) {
for(auto el: in1[i]) {
f[el.ff]=el.ss;
// debug(d[2].t);
recal((el.ff-1)/B);
}
for(auto el: in[i]) {
int s=q[el].s,t=q[el].t;
Node cur;
cur.hasY=0;
cur.s1=cur.t1=-1,
cur.s=cur.t=s;cur.len=1;cur.x=cur.y=0;
while(true) {
if (f[cur.t]==-1) {
ans[el]=-1;
break;
}
Node tmp=mrg(cur,d[f[cur.t]]);
if (tmp.len==-1 || tmp.t > t || pf[t-1]-pf[tmp.t-1]<=big[i-1]) {
while(true) {
if (f[cur.t]==-1) {
ans[el]=-1;
break;
}
Node sus;
sus.s1=sus.t1=-1,
sus.s=sus.t=f[cur.t];sus.len=1;sus.x=sus.y=0;
sus.hasY=0;
sus=mrg(cur,sus);
if (sus.len==-1) {
ans[el]=-1;
break;
}
cur=sus;
// if (cur.t==3) debug(cur.x,cur.y);
if (pf[t-1]-pf[cur.t-1]<=big[i-1]) break;
}
break;
}
cur=tmp;
}
if (ans[el]==-1 || cur.len==-1) continue;
while(true) {
Node tmp=mrg(cur,d[f[cur.t]]);
if (tmp.t>t || tmp.hasY || tmp.len==-1) {
while(true) {
if (b[f[cur.t]]>b[cur.t] || f[cur.t]==-1) break;
Node sus;
sus.s1=sus.t1=-1,
sus.s=sus.t=f[cur.t];sus.len=1;sus.x=sus.y=0;
sus.hasY=0;
sus=mrg(cur,sus);
if (sus.t>t) break;
cur=sus;
}
break;
}
cur=tmp;
}
// For(j,1,n) debug(f[j]);
if (cur.t==t) {
ll suc=cur.x+cur.y*big[i-1];
if (cur.len>1 && b[t]>b[cur.t1]) {
suc-=b[cur.t1]*(big[i-1]-pf[t-1]+pf[cur.t1-1]);
}
ans[el]=suc;
} else {
if (cur.len>1 && b[t]>b[cur.t1]) {
ll suc=cur.x+cur.y*big[i-1]+b[cur.t1]*(pf[t-1]-big[i-1]+pf[cur.t1-1]);
ans[el]=suc;
} else {
ll suc=cur.x+cur.y*big[i-1]+b[cur.t]*(pf[t-1]-pf[cur.t-1]);
ans[el]=suc;
}
}
}
}
For(i,1,m) cout << ans[i] << endl;
return 0;
}
# | 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... |