Submission #1185743

#TimeUsernameProblemLanguageResultExecution timeMemory
1185743avighnaBitaro, who Leaps through Time (JOI19_timeleap)C++20
0 / 100
3096 ms293268 KiB
#include <bits/stdc++.h> typedef long long ll; const ll inf = 1e15; struct Query { ll a, b, c, d; int i; }; template <typename T> class SparseTable { public: int max_p; std::vector<T> orig; std::vector<std::vector<T>> table; std::function<T(T, T)> f; SparseTable(const std::vector<T> &x, const std::function<T(T, T)> &f) : orig(x), f(f) { const int n = x.size(); max_p = std::floor(std::log2(n)); table = std::vector(max_p + 1, std::vector<T>(n)); for (int i = 0; i < n; ++i) { table[0][i] = x[i]; } for (int p = 1; p <= max_p; ++p) { for (int i = 0; i < n - (1 << (p - 1)); ++i) { table[p][i] = f(table[p - 1][i], table[p - 1][i + (1 << (p - 1))]); } } } T query(int a, int b) { if (a == b) { return orig[a]; } int p = std::ceil(std::log2(b - a + 1)) - 1; return f(table[p][a], table[p][b - (1 << p) + 1]); } }; std::vector<ll> solve(int n, int q, std::vector<ll> &l, std::vector<ll> &r, std::vector<Query> &queries) { l.push_back(inf); r.push_back(inf + 1); const int lim = std::log2(n) + 1; std::vector ansl(n, std::vector<std::pair<ll, ll>>(lim)), ansr(n, std::vector<std::pair<ll, ll>>(lim)); for (int i = 0; i < n; ++i) { ansl[i][0] = {0, l[i] + 1}; ansr[i][0] = {0, r[i]}; // 0 jumps means we don't need anything if (i != n - 1) { ll v1 = std::max(0LL, ansl[i][0].second - (r[i + 1] - 1)); ll v2 = std::max(0LL, ansr[i][0].second - (r[i + 1] - 1)); ansl[i][0].first += v1; ansr[i][0].first += v2; ansl[i][0].second -= v1; ansr[i][0].second -= v2; } } auto _ansl = [&](int i, int x) -> std::pair<ll, ll> { 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}; }; auto _ansr = [&](int i, int x) -> std::pair<ll, ll> { 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::vector<ll> orig_max(n), orig_min(n); for (int i = 0; i < n; ++i) { orig_max[i] = l[i] - i; orig_min[i] = r[i] - i - 1; } SparseTable<ll> table_max(orig_max, [&](ll a, ll b) { return std::max(a, b); }), table_min(orig_min, [&](ll a, ll b) { return std::min(a, b); }); auto _ans = [&](int i, int x, ll t) -> std::pair<ll, ll> { int idx1 = *std::ranges::partition_point(std::views::iota(i, n), [&](int j) { return table_max.query(i, j) <= t - i; }); // first index such that l <= t_then is not true int idx2 = *std::ranges::partition_point(std::views::iota(i, n), [&](int j) { return t - i <= table_min.query(i, j); }); // first index such that t_then <= r-1 is not true ll free_jumps = std::max(0, std::min(idx1, idx2) - i); if (x <= free_jumps) { int r_idx = i + x; std::pair<ll, ll> p = {0, t + x}; if (t + x > r[r_idx] - 1) { int del = t + x - (r[r_idx] - 1); p.first += del; p.second -= del; } return p; } // jump ahead how much ever we can if (idx1 < idx2) { auto p = _ansl(idx1, x - free_jumps); return {p.first, p.second}; } else { // we're to the right (>=) of r[idx2], we need to get to r[idx2]-1 ll t_cur = t + free_jumps; ll cost = t_cur - (r[idx2] - 1); // this does that auto p = _ansr(idx2, x - free_jumps); return {cost + p.first, p.second}; } }; for (int bt = 1; bt < lim; ++bt) { for (int i = 0; i + (1 << bt) < n; ++i) { { auto [ans1, t1] = ansl[i][bt - 1]; auto [ans2, t2] = _ans(i + (1 << (bt - 1)), 1 << (bt - 1), t1); ansl[i][bt] = {ans1 + ans2, t2}; } { auto [ans1, t1] = ansr[i][bt - 1]; auto [ans2, t2] = _ans(i + (1 << (bt - 1)), 1 << (bt - 1), t1); ansr[i][bt] = {ans1 + ans2, t2}; } } } std::vector<ll> ans(q); for (auto &[a, b, c, d, i] : queries) { if (a == c) { continue; } 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; } time++; if (time > d) { cost += time - d; } ans[i] = cost; } l.pop_back(); r.pop_back(); return ans; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<ll> l(n - 1), r(n - 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) { q1.push_back({a, b, c, d, i}); } else { q2.push_back({a, b, c, d, i}); } } auto ans1 = solve(n, q, l, r, q1); std::reverse(l.begin(), l.end()); std::reverse(r.begin(), r.end()); for (auto &[a, b, c, d, i] : q2) { a = n - a - 1, c = n - c - 1; } auto ans2 = solve(n, q, l, r, q2); for (int i = 0; i < q; ++i) { std::cout << std::max(ans1[i], ans2[i]) << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...