Submission #1230697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230697		zNatsumi	Triple Jump (JOI19_jumps)	C++20	100 / 100	800 ms	66772 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

#define int long long
using ii = pair<int, int>;

const int N = 5e5 + 5;

int n, q, a[N], st[N<<2], mx[N<<2], lz[N<<2], res[N];
vector<ii> query[N];

void build(int tl = 1, int tr = n, int i = 1){
  if(tl == tr){
    mx[i] = a[tl];
    return;
  }
  int tm = tl + tr >> 1;
  build(tl, tm, i<<1); build(tm + 1, tr, i<<1|1);
  mx[i] = max(mx[i<<1], mx[i<<1|1]);
}

void push(int i){
  if(!lz[i]) return;
  st[i<<1] = max(st[i<<1], lz[i] + mx[i<<1]);
  st[i<<1|1] = max(st[i<<1|1], lz[i] + mx[i<<1|1]);
  lz[i<<1] = max(lz[i<<1], lz[i]); lz[i<<1|1] = max(lz[i<<1|1], lz[i]); lz[i] = 0;
}

void update(int l, int r, int x, int tl = 1, int tr = n, int i = 1){
  if(r < tl || tr < l || l > r) return;
  if(l <= tl && tr <= r){
    st[i] = max(st[i], x + mx[i]);
    lz[i] = max(lz[i], x);
    return;
  }
  push(i);
  int tm = tl + tr >> 1;
  update(l, r, x, tl, tm, i<<1); update(l, r, x, tm + 1, tr, i<<1|1);
  st[i] = max(st[i<<1], st[i<<1|1]);
}

int get(int l, int r, int tl = 1, int tr = n, int i = 1){
  if(r < tl || tr < l || l > r) return 0;
  if(l <= tl && tr <= r) return st[i];
  push(i);
  int tm = tl + tr >> 1;
  return max(get(l, r, tl, tm, i<<1), get(l, r, tm + 1, tr, i<<1|1));
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  cin >> q;
  for(int i = 1; i <= q; i++){
    int l, r; cin >> l >> r;
    query[l].push_back({r, i});
  }
  build();
  stack<int> s;
  for(int i = n; i >= 1; i--){
    while(s.size()){
      update(2*s.top() - i, n, a[i] + a[s.top()]);
      if(a[s.top()] <= a[i]) s.pop();
      else break;
    }
    s.push(i);
    for(auto [r, idx] : query[i]) res[idx] = get(i, r);
  }
  for(int i = 1; i <= q; i++) cout << res[i] << "\n";
}

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