Submission #909867

#	Time	Username	Problem	Language	Result	Execution time	Memory
909867		nima_aryan	Triple Jump (JOI19_jumps)	C++17	100 / 100	947 ms	64120 KiB

jumps

/**
 *    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;
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54