Submission #909879

#	Time	Username	Problem	Language	Result	Execution time	Memory
909879		nima_aryan	Triple Jump (JOI19_jumps)	C++17	100 / 100	930 ms	52864 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;

struct Tag {
  int add = 0;

  void apply(const Tag& t) {
    add = max(add, t.add);
  }
};
struct Info {
  int val = 0;
  int best = 0;

  void apply(const Tag& t) {
    best = max(best, val + t.add);
  }
};
Info operator+(const Info& a, const Info& b) {
  return {max(a.val, b.val), max(a.best, b.best)};
}

struct LazySegmentTree {
  int n;
  vector<Info> info;
  vector<Tag> tag;

  LazySegmentTree(int n) : n(n) {
    info.assign(4 << __lg(n), Info());
    tag.assign(4 << __lg(n), Tag());
  }

  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]);
  }

  void modify(int p, int l, int r, int x, const Info& v) {
    if (r - l == 1) {
      info[p] = v;
      return;
    }
    push(p);
    int m = (l + r) / 2;
    if (x < m) {
      modify(2 * p, l, m, x, v);
    } else {
      modify(2 * p + 1, m, r, x, v);
    }
    pull(p);
  }
  void modify(int x, const Info& v) {
    modify(1, 0, n, x, v);
  }

  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;
    }
    push(p);
    int m = (l + r) / 2;
    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);
  }

  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];
    }
    push(p);
    int m = (l + r) / 2;
    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);
  }
};

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 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