#include <bits/stdc++.h>
#include <immintrin.h>
using namespace std;
using ll = long long;
using ld = long double;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
mt19937 mt(123);
void solve();
void init();
int32_t main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cout << fixed << setprecision(30);
init();
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
#define int ll
struct segment_tree {
vector<ll> st;
int sz;
segment_tree() = default;
segment_tree(vector<int> a) {
sz = 1;
while (sz < a.size()) {
sz <<= 1;
}
st.resize(2 * sz, 0);
for (int i = 0; i < a.size(); i++) {
st[sz + i] = a[i];
}
for (int i = sz - 1; i > 0; i--) {
st[i] = st[2 * i] + st[2 * i + 1];
}
}
void add(int i, ll x) {
i += sz;
while (i) {
st[i] += x;
i >>= 1;
}
}
ll get(int l, int r) {
l += sz;
r += sz;
ll res = 0;
while (l <= r) {
if (l & 1) {
res += st[l++];
}
if (~r & 1) {
res += st[r--];
}
l >>= 1;
r >>= 1;
}
return res;
}
};
struct mseg_tree {
segment_tree def, step;
int now_step;
mseg_tree() = default;
mseg_tree(int n) {
now_step = 0;
def = segment_tree(vector<int>(n, 0));
step = segment_tree(vector<int>(n, 0));
}
void add_def(int i, int x) {
def.add(i, x);
}
void add_step(int i, int x) {
step.add(i, x);
def.add(i, -1ll * x * now_step);
}
void next_step() {
now_step++;
}
void set_step(int new_step) {
now_step = new_step;
}
ll get(int l, int r) {
return def.get(l, r) + now_step * step.get(l, r);
}
};
struct sparse_max {
using Type = pair<int, int>;
vector<vector<Type>> sp;
vector<int> p;
sparse_max(const vector<Type>& a) {
int n = a.size(), lg = 1;
while ((1 << lg) < n) {
lg++;
}
sp.resize(lg, vector<Type>(n));
for (int i = 0; i < n; i++) {
sp[0][i] = a[i];
}
for (int l = 1; l < lg; l++) {
for (int i = 0; i <= n - (1 << l); i++) {
sp[l][i] = max(sp[l - 1][i], sp[l - 1][i + (1 << (l - 1))]);
}
}
int nw = 0;
p.resize(n + 1, 0);
for (int i = 1; i <= n; i++) {
if ((1 << nw) * 2 < i) {
nw++;
}
p[i] = nw;
}
}
Type get(int l, int r) {
int lev = p[r - l + 1];
return max(sp[lev][l], sp[lev][r - (1 << lev) + 1]);
}
};
struct segment_tree2 {
vector<ll> st1, st2, lazy;
int sz;
segment_tree2(const vector<int>& a) {
sz = 1;
while (sz < a.size()) {
sz <<= 1;
}
st1.resize(2 * sz);
st2.resize(2 * sz);
lazy.resize(2 * sz);
for (int i = 0; i < 2 * sz; i++) {
st1[i] = 0;
st2[i] = 0;
lazy[i] = 0;
}
for (int i = 0; i < a.size(); i++) {
st1[sz + i] = a[i];
}
for (int i = sz - 1; i > 0; i--) {
st1[i] = st1[2 * i] + st1[2 * i + 1];
}
}
void push(int i) {
if (i < sz && lazy[i]) {
st2[2 * i] = st1[2 * i] * lazy[i];
st2[2 * i + 1] = st1[2 * i + 1] * lazy[i];
lazy[2 * i] = lazy[i];
lazy[2 * i + 1] = lazy[i];
lazy[i] = 0;
}
}
void set(int l, int r, int v, int l1 = 0, int r1 = -1, int i = 1) {
if (r1 == -1) {
r1 += sz;
}
if (l1 >= l && r1 <= r) {
lazy[i] = v;
st2[i] = st1[i] * v;
return;
}
if (l1 > r || r1 < l) {
return;
}
push(i);
set(l, r, v, l1, (l1 + r1) / 2, 2 * i);
set(l, r, v, (l1 + r1) / 2 + 1, r1, 2 * i + 1);
st2[i] = st2[2 * i] + st2[2 * i + 1];
}
ll get(int l, int r, int l1 = 0, int r1 = -1, int i = 1) {
if (r1 == -1) {
r1 += sz;
}
if (l1 >= l && r1 <= r) {
return st2[i];
}
if (l1 > r || r1 < l) {
return 0;
}
push(i);
return get(l, r, l1, (l1 + r1) / 2, 2 * i) + get(l, r, (l1 + r1) / 2 + 1, r1, 2 * i + 1);
}
};
void init() {}
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n), w(n), nxt(n), prv(n), start_time(q);
vector<ll> pref(n + 1);
for (int i = 0; i < n; i++) {
cin >> w[i];
}
for (int i = 0; i < n; i++) {
cin >> a[i]; a[i] *= -1;
}
pref[0] = 0;
for (int i = 0; i < n; i++) {
pref[i + 1] = pref[i] + w[i];
}
mseg_tree st(n);
for (int i = 0; i < n; i++) {
st.add_step(i, a[i]);
}
vector<pair<int, int>> fsp(n), fsp2(n);
for (int i = 0; i < n; i++) {
fsp[i] = {a[i], -i};
fsp2[i] = {w[i], 0};
}
sparse_max sp(fsp), spw(fsp2);
vector<pair<int, pair<int, int>>> ev;
vector<pair<int, int>> qu;
vector<pair<int, int>> seg(q);
vector<ll> ans(q);
vector<vector<int>> start(n);
for (int i = 0; i < q; i++) {
int t, l, r;
cin >> l >> r >> t; l--; r--; t--;
qu.emplace_back(t, i);
seg[i] = {l, r};
start_time[i] = t;
start[l].push_back(i);
}
vector<pair<int, int>> stack(1, {INT32_MAX, n});
for (int i = n - 1; i >= 0; i--) {
while (a[i] >= stack.back().x) {
stack.pop_back();
}
nxt[i] = stack.back().y;
stack.emplace_back(a[i], i);
}
stack.clear(); stack.emplace_back(INT32_MAX, -1);
for (int i = 0; i < n; i++) {
while (a[i] > stack.back().x) {
stack.pop_back();
}
prv[i] = stack.back().y;
stack.emplace_back(a[i], i);
}
for (int i = 0; i < n; i++) {
ev.emplace_back(pref[nxt[i]] - pref[i], make_pair(i, -a[i]));
if (prv[i] != -1) {
ev.emplace_back(pref[i] - pref[prv[i]], make_pair(i, -a[i]));
ev.emplace_back(pref[nxt[i]] - pref[prv[i]], make_pair(i, a[i]));
}
}
sort(all(ev));
sort(all(qu));
int ptrev = 0, ptrqu = 0, t = 0;
while (ptrqu < qu.size()) {
while (ptrev < ev.size() && ev[ptrev].x == t) {
st.add_step(ev[ptrev].y.x, ev[ptrev].y.y);
ptrev++;
}
st.next_step();
while (ptrqu < qu.size() && qu[ptrqu].x == t) {
int i = qu[ptrqu++].y;
auto [l, r] = seg[i];
ll lans = 0, rans = 0;
if (pref[l] + t < pref[r]) {
{
int left = l, right = n;
while (right - left > 1) {
int mid = (right + left) / 2;
if (pref[mid] - pref[l] > t) {
right = mid;
} else {
left = mid;
}
}
auto [mx, mxi] = sp.get(l, left);
mxi *= -1;
lans = st.get(mxi + 1, n - 1);
ll lst = min(pref[mxi] + t, pref[nxt[mxi]] - 1);
lans += 1ll * (lst - pref[l] - t + 1) * mx;
}
if (r < n) {
int left = -1, right = r;
while (right - left > 1) {
int mid = (right + left) / 2;
if (pref[r] - pref[mid] > t) {
left = mid;
} else {
right = mid;
}
}
auto [mx, mxi] = sp.get(right, r);
mxi *= -1;
rans = st.get(mxi + 1, n - 1);
ll lst = min(pref[mxi] + t, pref[nxt[mxi]] - 1);
rans += 1ll * (lst - pref[r] + 1) * mx;
}
}
ans[i] = lans - rans;
}
if (ptrqu == qu.size()) {
break;
}
if (ptrev = ev.size()) {
t = qu[ptrqu].x;
} else {
t = min(qu[ptrqu].x, ev[ptrev].x);
}
}
segment_tree2 st2(w);
for (int pos = n - 1; pos >= 0; pos--) {
st2.set(pos, nxt[pos] - 1, a[pos]);
for (int i : start[pos]) {
auto [l, r] = seg[i];
int t = min(1ll * start_time[i], pref[r] - pref[l]);
int left = l, right = n;
while (right - left > 1) {
int mid = (right + left) / 2;
if (pref[mid] - pref[l] > t) {
right = mid;
} else {
left = mid;
}
}
ll weight = st2.get(left, left) / w[left];
ans[i] += st2.get(l, left - 1) + weight * (pref[l] + t - pref[left]);
}
}
for (int i = 0; i < q; i++) {
if (spw.get(seg[i].x, seg[i].y - 1).x <= start_time[i] + 1) {
cout << -ans[i] << '\n';
} else {
cout << "-1\n";
}
}
}
Compilation message
Main.cpp: In constructor 'segment_tree::segment_tree(std::vector<long long int>)':
Main.cpp:39:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | while (sz < a.size()) {
| ~~~^~~~~~~~~~
Main.cpp:43:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
Main.cpp: In constructor 'segment_tree2::segment_tree2(const std::vector<long long int>&)':
Main.cpp:140:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | while (sz < a.size()) {
| ~~~^~~~~~~~~~
Main.cpp:151:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
151 | for (int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:266:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
266 | while (ptrqu < qu.size()) {
| ~~~~~~^~~~~~~~~~~
Main.cpp:267:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
267 | while (ptrev < ev.size() && ev[ptrev].x == t) {
| ~~~~~~^~~~~~~~~~~
Main.cpp:272:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
272 | while (ptrqu < qu.size() && qu[ptrqu].x == t) {
| ~~~~~~^~~~~~~~~~~
Main.cpp:312:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
312 | if (ptrqu == qu.size()) {
| ~~~~~~^~~~~~~~~~~~
Main.cpp:315:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
315 | if (ptrev = ev.size()) {
| ~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
101 ms |
44484 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
503 ms |
187768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
