Submission #868927

#TimeUsernameProblemLanguageResultExecution timeMemory
868927rockstarTriple Jump (JOI19_jumps)C++17
100 / 100
958 ms136528 KiB
//#pragma GCC optimize("O3,unroll-loops,inline,fast-math") #include <bits/stdc++.h> using namespace std; using ll = long long; #define all(a) (a).begin(), (a).end() #define int ll constexpr int INF = numeric_limits<int>::max() / 2; struct node { int c = 0, res = 0; node(int a) { c = a; res = -INF; } node() {} }; node operator+(node a, node b) { node x; x.res = max(a.res, b.res); x.c = max(a.c, b.c); return x; } struct segment_tree { vector<node> tree; vector<int> maxupd; int n; segment_tree(vector<int> &a) { n = a.size(); tree.resize(4 * n); maxupd.resize(4 * n, -INF); build(1, 0, n - 1, a); } void build(int v, int tl, int tr, vector<int> &a) { if (tl == tr) { tree[v] = node(a[tl]); return; } int tm = (tl + tr) / 2; build(2 * v, tl, tm, a); build(2 * v + 1, tm + 1, tr, a); tree[v] = tree[v * 2] + tree[v * 2 + 1]; } void push(int v, int tl, int tr) { if (tl != tr) maxupd[v * 2] = max(maxupd[v * 2], maxupd[v]), maxupd[v * 2 + 1] = max(maxupd[v * 2 + 1], maxupd[v]); tree[v].res = max(tree[v].res, tree[v].c + maxupd[v]); } void upd(int v, int tl, int tr, int l, int r, int val) { push(v, tl, tr); if (r < tl || tr < l) return; if (l <= tl && tr <= r) { maxupd[v] = max(maxupd[v], val); push(v, tl, tr); return; } int tm = (tl + tr) / 2; upd(v * 2, tl, tm, l, r, val); upd(v * 2 + 1, tm + 1, tr, l, r, val); tree[v] = tree[v * 2] + tree[v * 2 + 1]; } int get(int v, int tl, int tr, int l, int r) { push(v, tl, tr); if (r < tl || tr < l) return 0; if (l <= tl && tr <= r) return tree[v].res; int tm = (tl + tr) / 2; return max(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r)); } void upd(int l, int val) { upd(1, 0, n - 1, l, n - 1, val); } int get(int l, int r) { return get(1, 0, n - 1, l, r); } }; void solve() { int n; cin >> n; vector<int> a(n); for (int &i: a) cin >> i; vector<pair<int, int>> st; vector<vector<pair<int, int>>> ab(n); for (int i = 0; i < n; ++i) { while (!st.empty() && st.back().first <= a[i]) { if (2 * i - st.back().second < n) ab[st.back().second].push_back({i, st.back().first + a[i]}); st.pop_back(); } if (!st.empty()) { if (2 * i - st.back().second < n) ab[st.back().second].push_back({i, st.back().first + a[i]}); } st.push_back({a[i], i}); } int q; cin >> q; vector<vector<pair<int, int>>> query(n); for (int i = 0; i < q; ++i) { int l, r; cin >> l >> r; --l, --r; query[l].push_back({r, i}); } segment_tree tr(a); vector<int> res(q); for (int i = n - 1; i >= 0; --i) { for (auto [b, sum]: ab[i]) tr.upd(2 * b - i, sum); for (auto [r, ind] : query[i]) res[ind] = tr.get(i, r); } for (int i : res) cout << i << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...