#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 201010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
typedef pair<ll, int> pli;
pll operator+(pll p1, pll p2) {
return pll(p1.first + p2.first, p1.second + p2.second);
}
pll operator-(pll p1) {
return pll(-p1.first, -p1.second);
}
struct fenwick {
vector<pll> tree;
int N;
fenwick(int N = 0) :N(N) { tree.resize(N + 1); }
void upd(int i, pll x) { while (i <= N) { tree[i] = tree[i] + x, i += i & -i; } }
pll get(int i) { pll ans = pll(0, 0); while (i) { ans = ans + tree[i], i -= i & -i; } return ans; }
void update(int l, int r, pll x) {
if (r <= 0) return;
if (l > r) return;
upd(l, x);
if (r <= N) upd(r + 1, -x);
}
};
struct segtree {
int N;
vector<pii> tree, arr;
int mod = 0;
pii zero;
segtree(int N = 0, int mod = 0) :N(N), mod(mod) {
tree.resize(N << 2);
zero = mod ? pii(1e9, 0) : pii(0, 0);
arr = {};
}
void init(int l, int r, int loc = 1) {
if (l == r) {
tree[loc] = arr[l];
return;
}
int m = l + r >> 1;
init(l, m, loc * 2);
init(m + 1, r, loc * 2 + 1);
if (mod) tree[loc] = min(tree[loc * 2], tree[loc * 2 + 1]);
else tree[loc] = max(tree[loc * 2], tree[loc * 2 + 1]);
}
pii query(int s, int e, int l, int r, int loc = 1) {
if (e < l || r < s) return zero;
if (l <= s && e <= r) return tree[loc];
int m = s + e >> 1;
if (mod) return min(query(s, m, l, r, loc * 2), query(m + 1, e, l, r, loc * 2 + 1));
else return max(query(s, m, l, r, loc * 2), query(m + 1, e, l, r, loc * 2 + 1));
}
pii query(int l, int r) { return query(1, N, l, r); }
};
struct query {
int ind;
ll U;
int mul;
};
ll A[MAX];
ll X[MAX];
ll B[MAX];
ll S[MAX];
ll T[MAX];
ll U[MAX];
ll ans[MAX];
int L[MAX];
int R[MAX];
vector<int> ls[MAX];
int N, M, K;
vector<ll> Us;
segtree segA, segB;
fenwick bit;
vector<query> qv[MAX];
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> N >> M;
int i;
for (i = 1; i <= N; i++) cin >> A[i], X[i + 1] = X[i] + A[i];
for (i = 1; i <= N; i++) cin >> B[i];
for (i = 1; i <= M; i++) cin >> S[i] >> T[i] >> U[i], Us.push_back(U[i]);
Us.push_back(0);
sort(Us.begin(), Us.end());
Us.erase(unique(Us.begin(), Us.end()), Us.end());
K = Us.size();
bit = fenwick(K);
segA = segtree(N, 0);
segB = segtree(N, 1);
segA.arr.push_back(pii(0, 0));
segB.arr.push_back(pii(0, 0));
for (i = 1; i <= N; i++) segA.arr.push_back(pii(A[i], i));
for (i = 1; i <= N; i++) segB.arr.push_back(pii(B[i], i));
segA.init(1, N);
segB.init(1, N);
for (i = 1; i <= M; i++) {
if (segA.query(S[i], T[i] - 1).first > U[i]) {
ans[i] = -1;
continue;
}
if (T[i] == N + 1) qv[S[i]].push_back({ i, U[i], 1 });
else {
int ind = lower_bound(X + 1, X + N + 2, X[T[i]] - U[i]) - X;
int t1 = segB.query(ind, T[i]).second;
qv[S[i]].push_back({ i, U[i], 1 });
qv[t1].push_back({ i, U[i], -1 });
ans[i] = X[T[i]] - X[t1];
ans[i] *= B[t1];
}
}
for (i = 1; i <= N; i++) L[i] = 0, R[i] = N + 1;
vector<pli> st;
st.emplace_back(0, 0);
for (i = 1; i <= N; i++) {
while (st.back().first > B[i]) st.pop_back();
L[i] = st.back().second;
st.emplace_back(B[i], i);
}
st.clear();
st.emplace_back(0, N + 1);
for (i = N; i >= 1; i--) {
while (st.back().first >= B[i]) st.pop_back();
R[i] = st.back().second;
st.emplace_back(B[i], i);
}
for (i = 1; i <= N; i++) ls[L[i]].push_back(i);
for (i = N; i >= 1; i--) {
int ind = lower_bound(Us.begin(), Us.end(), X[R[i]] - X[i]) - Us.begin();
bit.update(1, ind - 1, pll(B[i], B[i] * X[i]));
bit.update(ind, K, pll(0, B[i] * X[R[i]]));
bit.update(1, K, pll(0, -X[i] * B[i]));
for (auto v : ls[i]) {
int ind1 = lower_bound(Us.begin(), Us.end(), X[v] - X[i]) - Us.begin();
int ind2 = lower_bound(Us.begin(), Us.end(), X[R[v]] - X[i]) - Us.begin();
bit.update(1, K, pll(0, X[v] * B[v]));
bit.update(1, ind1 - 1, pll(0, -B[v] * X[v]));
bit.update(ind1, ind2 - 1, pll(-B[v], -B[v] * X[i]));
bit.update(ind2, K, pll(0, -B[v] * X[R[v]]));
}
for (auto& [ind, U, mul] : qv[i]) {
int uind = lower_bound(Us.begin(), Us.end(), U) - Us.begin();
auto res = bit.get(uind);
ans[ind] += mul * (res.first * U + res.second);
}
}
for (i = 1; i <= M; i++) cout << ans[i] << ln;
}
Compilation message
Main.cpp: In member function 'void segtree::init(int, int, int)':
Main.cpp:48:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
48 | int m = l + r >> 1;
| ~~^~~
Main.cpp: In member function 'pii segtree::query(int, int, int, int, int)':
Main.cpp:57:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | int m = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
10680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
24116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
408 ms |
60700 KB |
Output is correct |
| 2 |
Correct |
329 ms |
67052 KB |
Output is correct |
| 3 |
Correct |
304 ms |
62676 KB |
Output is correct |
| 4 |
Correct |
395 ms |
60776 KB |
Output is correct |
| 5 |
Correct |
307 ms |
61932 KB |
Output is correct |
| 6 |
Correct |
323 ms |
65664 KB |
Output is correct |
| 7 |
Correct |
381 ms |
58240 KB |
Output is correct |
| 8 |
Correct |
306 ms |
63388 KB |
Output is correct |
| 9 |
Correct |
295 ms |
59672 KB |
Output is correct |
| 10 |
Correct |
183 ms |
62388 KB |
Output is correct |
| 11 |
Correct |
303 ms |
60408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
10680 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
