제출 #909867

#제출 시각아이디문제언어결과실행 시간메모리
909867nima_aryan3단 점프 (JOI19_jumps)C++17
100 / 100
947 ms64120 KiB
/** * author: NimaAryan * created: 2024-01-16 23:23:10 **/ #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "algo/debug.h" #endif using i64 = long long; template <class Info, class Tag> class LazySegmentTree { public: std::vector<Info> info; std::vector<Tag> tag; int n; LazySegmentTree() : n(0) {} LazySegmentTree(int n_, Info v_ = Info()) { init(n_, v_); } LazySegmentTree(std::vector<Info> init_) { init(init_); } void init(int n_, Info v_ = Info()) { init(std::vector(n_, v_)); } void init(std::vector<Info> init_) { n = (int) init_.size(); info.assign(4 << std::__lg(n), Info()); tag.assign(4 << std::__lg(n), Tag()); std::function<void(int, int, int)> build; build = [&](int p, int l, int r) { if (r - l == 1) { info[p] = init_[l]; return; } int m = (l + r) / 2; build(2 * p, l, m); build(2 * p + 1, m, r); pull(p); }; build(1, 0, n); } void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; } void apply(int p, const Tag& v) { info[p].apply(v); tag[p].apply(v); } void push(int p) { apply(2 * p, tag[p]); apply(2 * p + 1, tag[p]); tag[p] = Tag(); } void modify(int p, int l, int r, int x, const Info& v) { if (r - l == 1) { info[p] = v; return; } int m = (l + r) / 2; push(p); if (x < m) { modify(2 * p, l, m, x, v); } else { modify(2 * p + 1, m, r, x, v); } pull(p); } void modify(int p, const Info& v) { modify(1, 0, n, p, v); } Info range_query(int p, int l, int r, int lx, int rx) { if (l >= rx || r <= lx) { return Info(); } if (l >= lx && r <= rx) { return info[p]; } int m = (l + r) / 2; push(p); return range_query(2 * p, l, m, lx, rx) + range_query(2 * p + 1, m, r, lx, rx); } Info range_query(int lx, int rx) { return range_query(1, 0, n, lx, rx); } void range_apply(int p, int l, int r, int lx, int rx, const Tag& v) { if (l >= rx || r <= lx) { return; } if (l >= lx && r <= rx) { apply(p, v); return; } int m = (l + r) / 2; push(p); range_apply(2 * p, l, m, lx, rx, v); range_apply(2 * p + 1, m, r, lx, rx, v); pull(p); } void range_apply(int lx, int rx, const Tag& v) { range_apply(1, 0, n, lx, rx, v); } template <class F = std::function<bool(const Info&)>> int find_first(int p, int l, int r, int lx, int rx, F pred) { if (l >= rx || r <= lx || !pred(info[p])) { return -1; } if (r - l == 1) { return l; } int m = (l + r) / 2; push(p); int res = find_first(2 * p, l, m, lx, rx, pred); if (res == -1) { res = find_first(2 * p + 1, m, r, lx, rx, pred); } return res; } template <class F = std::function<bool(const Info&)>> int find_first(int lx, int rx, F pred) { return find_first(1, 0, n, lx, rx, pred); } template <class F = std::function<bool(const Info&)>> int find_last(int p, int l, int r, int lx, int rx, F pred) { if (l >= rx || r <= lx || !pred(info[p])) { return -1; } if (r - l == 1) { return l; } int m = (l + r) / 2; push(p); int res = find_last(2 * p + 1, m, r, lx, rx, pred); if (res == -1) { res = find_last(2 * p, l, m, lx, rx, pred); } return res; } template <class F = std::function<bool(const Info&)>> int find_last(int lx, int rx, F pred) { return find_last(1, 0, n, lx, rx, pred); } }; struct Tag { int add = 0; void apply(Tag t) { add = max(add, t.add); } }; struct Info { int val = 0; int best = 0; void apply(Tag t) { best = max(best, val + t.add); } }; Info operator+(Info a, Info b) { return {max(a.val, b.val), max(a.best, b.best)}; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } int q; cin >> q; vector<int> l(q), r(q); vector<vector<int>> qs(n); for (int i = 0; i < q; ++i) { cin >> l[i] >> r[i]; --l[i]; qs[l[i]].push_back(i); } vector<int> ans(q); LazySegmentTree<Info, Tag> seg(n); for (int i = 0; i < n; ++i) { seg.modify(i, {a[i], 0}); } vector<int> stk; for (int i = n - 1; i >= 0; --i) { while (!stk.empty()) { int j = stk.back(); stk.pop_back(); seg.range_apply(j + (j - i), n, Tag{a[i] + a[j]}); if (a[j] > a[i]) { stk.push_back(j); break; } } stk.push_back(i); for (int p : qs[i]) { ans[p] = seg.range_query(i, r[p]).best; } } for (int i = 0; i < q; ++i) { cout << ans[i] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...