#include <bits/stdc++.h>
typedef long long ll;
const ll inf = 1e15;
struct Query {
ll a, b, c, d;
int i;
};
const int N = 3e5 + 1;
const int lim = 17;
ll l[N], r[N], ans[N], jump_min[N][lim], jump_max[N][lim];
std::pair<ll, ll> ansl[N][lim], ansr[N][lim];
int n, q;
std::pair<ll, ll> _ansl(int i, int x) {
ll cost = 0, time = l[i];
for (int bt = 0; bt < lim; ++bt) {
if (x & (1 << bt)) {
cost += ansl[i][bt].first;
time = ansl[i][bt].second;
i += (1 << bt);
}
}
return {cost, time};
}
std::pair<ll, ll> _ansr(int i, int x) {
ll cost = 0, time = r[i] - 1;
for (int bt = 0; bt < lim; ++bt) {
if (x & (1 << bt)) {
cost += ansr[i][bt].first;
time = ansr[i][bt].second;
i += (1 << bt);
}
}
return {cost, time};
}
std::pair<ll, ll> _ans(int i, int x, ll t) {
int idx1 = i, idx2 = i;
ll max_val = l[i] - i, min_val = r[i] - i - 1;
for (int bt = lim - 1; bt >= 0; --bt) {
ll m1 = std::max(max_val, jump_max[idx1 + 1][bt]),
m2 = std::min(min_val, jump_min[idx2 + 1][bt]);
if (idx1 + (1 << bt) < n and m1 <= t - i) {
max_val = m1;
idx1 += 1 << bt;
}
if (idx2 + (1 << bt) < n and t - i <= m2) {
min_val = m2;
idx2 += 1 << bt;
}
}
if (max_val <= t - i) {
idx1 = std::min(n, idx1 + 1);
}
if (t - i <= min_val) {
idx2 = std::min(n, idx2 + 1);
}
ll free_jumps = std::max(0, std::min(idx1, idx2) - i);
if (x <= free_jumps) {
ll del = std::max(0LL, t + x - (r[i + x] - 1));
return {del, t + x - del};
}
if (idx1 < idx2) {
return _ansl(idx1, x - free_jumps);
} else {
auto p = _ansr(idx2, x - free_jumps);
return {t + free_jumps - r[idx2] + p.first + 1, p.second};
}
}
void solve(std::vector<Query> &queries) {
for (int i = 0; i < n; ++i) {
ll v1 = std::max(0LL, l[i] - r[i + 1] + 2);
ll v2 = std::max(0LL, r[i] - r[i + 1] + 1);
ansl[i][0] = {v1, l[i] - v1 + 1};
ansr[i][0] = {v2, r[i] - v2};
jump_max[i][0] = l[i] - i;
jump_min[i][0] = r[i] - i - 1;
}
for (int bt = 1; bt < lim; ++bt) {
for (int i = 0; i < n; ++i) {
jump_min[i][bt] = jump_min[i][bt - 1];
jump_max[i][bt] = jump_max[i][bt - 1];
if (i + (1 << (bt - 1)) < n) {
jump_min[i][bt] =
std::min(jump_min[i][bt], jump_min[i + (1 << (bt - 1))][bt - 1]);
jump_max[i][bt] =
std::max(jump_max[i][bt], jump_max[i + (1 << (bt - 1))][bt - 1]);
auto [ans1, t1] =
_ans(i + (1 << (bt - 1)), 1 << (bt - 1), ansl[i][bt - 1].second);
auto [ans2, t2] =
_ans(i + (1 << (bt - 1)), 1 << (bt - 1), ansr[i][bt - 1].second);
ansl[i][bt] = {ansl[i][bt - 1].first + ans1, t1};
ansr[i][bt] = {ansr[i][bt - 1].first + ans2, t2};
}
}
}
for (auto &[a, b, c, d, i] : queries) {
auto [cost, time] = _ans(a, c - a - 1, b);
if (time < l[c - 1]) {
time = l[c - 1];
} else if (time > r[c - 1] - 1) {
cost += time - r[c - 1] + 1;
time = r[c - 1] - 1;
}
if (++time > d) {
cost += time - d;
}
ans[i] = std::max(ans[i], cost);
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> q;
l[n - 1] = inf, r[n - 1] = inf + 1;
for (int i = 0; i < n - 1; ++i) {
std::cin >> l[i] >> r[i];
}
std::vector<Query> q1, q2;
for (int i = 0, a, b, c, d, t; i < q; ++i) {
std::cin >> t >> a >> b >> c >> d;
--a, --c;
if (a == c) {
continue;
}
if (a < c) {
q1.push_back({a, b, c, d, i});
} else {
q2.push_back({n - a - 1, b, n - c - 1, d, i});
}
}
solve(q1);
std::reverse(l, l + n - 1);
std::reverse(r, r + n - 1);
solve(q2);
for (int i = 0; i < q; ++i) {
std::cout << ans[i] << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |