Submission #1085333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085333		rxlfd314	Triple Jump (JOI19_jumps)	C++17	100 / 100	471 ms	87376 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr int mxN = 500005;
int N, Q, A[mxN];
vt<ari2> queries[mxN];
vt<int> bs[mxN];

struct ST {
  struct Node {
    int ans, c, ab;
    Node operator+(const Node &other) {
      return {
        max({ans, other.ans, ab + other.c}), 
        max(c, other.c),
        max(ab, other.ab)
      };
    }
  } st[mxN<<1];
  void build() {
    FOR(i, 0, N-1)
      st[i+N] = {0, A[i], 0};
    ROF(i, N-1, 1)
      st[i] = st[i<<1] + st[i<<1|1];
  }
  void update(int i, int v) {
    i += N;
    st[i].ab = max(st[i].ab, v);
    st[i].ans = st[i].ab + st[i].c;
    for (i >>= 1; i > 0; i >>= 1)
      st[i] = st[i<<1] + st[i<<1|1];
  }
  Node query(int l, int r) {
    Node lft = {0, 0, 0}, rht = {0, 0, 0};
    for (l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
      if (l & 1)
        lft = lft + st[l++];
      if (r & 1)
        rht = st[--r] + rht;
    }
    return lft + rht;
  }
} st;

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cin >> N;
  FOR(i, 0, N-1)
    cin >> A[i];
  
  cin >> Q;
  FOR(i, 0, Q-1) {
    int l, r; cin >> l >> r, l--, r--;
    queries[l].push_back({r, i});
  }
  
  vt<int> sk;
  FOR(i, 0, N-1) {
    while (size(sk) && A[sk.back()] <= A[i]) {
      bs[sk.back()].push_back(i);
      sk.pop_back();
    }
    if (size(sk))
      bs[sk.back()].push_back(i);
    sk.push_back(i);
  }
  
  st.build();
  vt<int> ans(Q);
  ROF(i, N-3, 0) {
    for (int j : bs[i]) {
      if (2 * j - i >= N)
        continue;
      st.update(2 * j - i, A[i] + A[j]);
    }
    for (auto [r, qi] : queries[i])
      ans[qi] = st.query(i, r).ans;
  }
  
  for (auto &i : ans)
    cout << i << '\n';
}

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