#include <bits/stdc++.h>
using namespace std;
const int N = 200001;
const int L = __lg(N) + 1;
struct segtree {
segtree *left, *right;
long long sum, lazy, count;
segtree(int l, int r, long long *a) {
lazy = 0;
if (l + 1 == r) {
count = a[l + 1] - a[l];
sum = 0;
} else {
int m = (l + r) / 2;
left = new segtree(l, m, a);
right = new segtree(m, r, a);
pull();
}
}
void apply(long long x) {
sum += count * x, lazy += x;
}
void pull() {
sum = left->sum + right->sum;
count = left->count + right->count;
}
void push() {
if (lazy != 0) {
left->apply(lazy);
right->apply(lazy);
lazy = 0;
}
}
void update(int a, int b, long long x, int l, int r) {
if (a == b || b <= l || r <= a) {
return;
} else if (a <= l && r <= b) {
apply(x);
} else {
push();
int m = (l + r) / 2;
left->update(a, b, x, l, m);
right->update(a, b, x, m, r);
pull();
}
}
long long query(int a, int b, int l, int r) {
if (a == b || b <= l || r <= a) {
return 0;
} else if (a <= l && r <= b) {
return sum;
} else {
push();
int m = (l + r) / 2;
return left->query(a, b, l, m) + right->query(a, b, m, r);
}
}
};
int max_a[L][N], b[N], nxt[N], prv[N], k;
long long a[N], ans[N], values[4 * N];
array<int, 2> min_b[L][N];
vector<array<long long, 3>> updates[N];
vector<array<int, 3>> queries[N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> a[i];
max_a[0][i] = a[i];
}
for (int i = 0; i < n; ++i) {
cin >> b[i];
min_b[0][i] = {b[i], i};
}
for (int i = 1; i <= __lg(n); ++i) {
for (int j = 0; j + (1 << i) <= n; ++j) {
max_a[i][j] = max(max_a[i - 1][j], max_a[i - 1][j + (1 << (i - 1))]);
min_b[i][j] = min(min_b[i - 1][j], min_b[i - 1][j + (1 << (i - 1))]);
}
}
partial_sum(a, a + n, a);
rotate(a, a + n, a + n + 1);
for (int i = 0; i < m; ++i) {
int s, t, u;
cin >> s >> t >> u;
--s, --t;
int l = __lg(t - s);
if (max(max_a[l][s], max_a[l][t - (1 << l)]) <= u) {
//int v = lower_bound(a + s, a + t, a[t] - u) - a;
//l = __lg(t - v);
//v = min(min_b[l][v], min_b[l][t - (1 << l)])[1];
//ans[i] = (a[t] - a[v]) * b[v];
queries[s].push_back({u, 1, i});
//queries[v].push_back({u, -1, i});
} else {
ans[i] = -1;
}
}
vector<int> stack;
for (int i = 0; i < n; ++i) {
while (!stack.empty() && b[stack.back()] > b[i]) {
nxt[stack.back()] = i;
stack.pop_back();
}
prv[i] = stack.empty() ? -1 : stack.back();
stack.push_back(i);
}
for (auto i : stack) {
nxt[i] = n;
}
for (int i = n - 1; i >= 0; --i) {
updates[i].push_back({0, a[nxt[i]] - a[i], b[i]});
if (prv[i] >= 0) {
updates[prv[i]].push_back({a[i] - a[prv[i]], a[nxt[i]] - a[prv[i]], -b[i]});
}
for (auto &j : updates[i]) {
values[k++] = j[0], values[k++] = j[1];
}
for (auto &j : queries[i]) {
values[k++] = j[0];
}
}
sort(values, values + k);
k = unique(values, values + k) - values;
segtree *sum = new segtree(0, k, values);
for (int i = n - 1; i >= 0; --i) {
for (auto [l, r, x] : updates[i]) {
l = lower_bound(values, values + k, l) - values;
r = lower_bound(values, values + k, r) - values;
sum->update(l, r, x, 0, k);
}
for (auto [u, t, j] : queries[i]) {
u = lower_bound(values, values + k, u) - values;
ans[j] += t * sum->query(0, u, 0, k);
}
}
for (int i = 0; i < m; ++i) {
cout << ans[i] << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
11628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
110 ms |
35104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1051 ms |
110572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
11628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
