#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
typedef long long lint;
typedef pair<lint, lint> ii;
const lint inf = 1e16;
const int N = 215;
int n, Q;
lint X[N];
lint B[N];
lint R[N];
lint ans[N];
struct query{ lint U, id, mul; };
vector<query> queries[N];
vector<lint> dis;
int get(lint i){ return upper_bound(all(dis), i) - dis.begin(); }
struct seg{
lint tree[2*N];
lint query(int i){
lint res = 0;
for(i += N;i > 0;i >>= 1) res += tree[i];
return res;
}
void update(int l, int r, lint x){
for(l += N, r += N+1;l < r;l >>= 1, r >>= 1){
if(l&1) tree[l++] += x;
if(r&1) tree[--r] += x;
}
}
} m, c;
struct segmax{
lint tree[2*N];
lint query(int l, int r){
lint res = -inf;
for(l += N, r += N+1;l < r;l >>= 1, r >>= 1){
if(l&1) res = max(res, tree[l++]);
if(r&1) res = max(res, tree[--r]);
}
return res;
}
void update(int i, lint x){
for(i += N;i > 0;i >>= 1) tree[i] = max(tree[i], x);
}
} finddie;
struct segmin{
ii tree[2*N];
ii query(int l, int r){
ii res = ii(inf,inf);
for(l += N, r += N+1;l < r;l >>= 1, r >>= 1){
if(l&1) res = min(res, tree[l++]);
if(r&1) res = min(res, tree[--r]);
}
return res;
}
void update(int i, ii x){
for(i += N;i > 0;i >>= 1) tree[i] = min(tree[i], x);
}
} getmin;
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> Q;
for(int i = 2;i <= n+1;i++) cin >> X[i];
for(int i = 1;i <= n;i++) cin >> B[i];
fill(m.tree,m.tree + N*2,0); fill(c.tree,c.tree + N*2,0);
fill(getmin.tree,getmin.tree + 2*N, ii(inf,inf));
for(int i = 2;i <= n+1;i++) finddie.update(i-1, X[i]);
for(int i = 1;i <= n;i++) getmin.update(i, ii(B[i],i));
for(int i = 2;i <= n+1;i++) X[i] += X[i-1];
for(int q = 1;q <= Q;q++){
int s, t, u; cin >> s >> t >> u;
if(finddie.query(s,t-1) > u) ans[q] = -1;
else{
queries[s].push_back({u,q,1});
int findpos = lower_bound(X+1, X+n+1, X[t] - u) - X;
lint tmiddle = getmin.query(max(s,findpos),t-1).second;
queries[tmiddle].push_back({u,q,-1});
ans[q] += (X[t]-X[tmiddle]) * B[tmiddle];
dis.push_back(u);
}
}
dis.push_back(inf);
sort(all(dis));
dis.erase(unique(all(dis)), dis.end());
stack<int> st;
B[n+1] = -inf; st.push(n+1);
lint maxdis = 0;
for(int s = n;s >= 1;s--){
maxdis = max(maxdis, X[s+1]-X[s]);
while(B[st.top()] >= B[s]){
///do something about st.top()
int i = st.top();
lint d1 = get(X[i] - X[s]);
lint d2 = get(X[R[i]] - X[s]);
m.update(d1+1, d2, -B[i]);
c.update(d1+1,d2, (X[i]-X[s]) * B[i]);
c.update(d2+1,N-1, (X[R[i]]-X[i]) * -B[i]);
st.pop();
}
///add the min(Xi+U, Ri)
int r = st.top();
R[s] = r;
lint D = get(X[r] - X[s]);
m.update(1, D, B[s]);
c.update(D+1, N-1, (X[r]-X[s]) * B[s]);
st.push(s);
for(query &q : queries[s]){
ans[q.id] += q.mul * (m.query(get(q.U)) * q.U + c.query(get(q.U)));
}
}
for(int q = 1;q <= Q;q++) cout << ans[q] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
