Submission #1034657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034657		juicy	Triple Jump (JOI19_jumps)	C++17	100 / 100	642 ms	52548 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 5e5 + 5;

int n, q;
int a[N], s[4 * N], mx[4 * N], lz[4 * N], res[N];

void bld(int id = 1, int l = 1, int r = n) {
  if (l == r) {
    mx[id] = a[l];
    return;
  }
  int md = (l + r) / 2;
  bld(id * 2, l, md);
  bld(id * 2 + 1, md + 1, r);
  mx[id] = max(mx[id * 2], mx[id * 2 + 1]);
}

void app(int id, int x) {
  s[id] = max(s[id], mx[id] + x);
  lz[id] = max(lz[id], x);
}

void psh(int id) {
  if (lz[id]) {
    app(id * 2, lz[id]);
    app(id * 2 + 1, lz[id]);
    lz[id] = 0;
  }
}

void upd(int u, int v, int x, int id = 1, int l = 1, int r = n) {
  if (u <= l && r <= v) {
    app(id, x);
    return;
  }
  psh(id);
  int md = (l + r) / 2;
  if (u <= md) {
    upd(u, v, x, id * 2, l, md);
  }
  if (md < v) {
    upd(u, v, x, id * 2 + 1, md + 1, r);
  }
  s[id] = max(s[id * 2], s[id * 2 + 1]);
}

int qry(int u, int v, int id = 1, int l = 1, int r = n) {
  if (u <= l && r <= v) {
    return s[id];
  }
  psh(id);
  int md = (l + r) / 2;
  if (v <= md) {
    return qry(u, v, id * 2, l, md);
  }
  if (md < u) {
    return qry(u, v, id * 2 + 1, md + 1, r);
  }
  return max(qry(u, v, id * 2, l, md), qry(u, v, id * 2 + 1, md + 1, r));
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n;
  vector<int> st;
  vector<array<int, 2>> cands;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    while (st.size() && a[st.back()] < a[i]) {
      st.pop_back();
    }
    if (st.size()) {
      cands.push_back({st.back(), i});
    }
    st.push_back(i);
  }  
  bld();
  st.clear();
  for (int i = n; i > 0; --i) {
    while (st.size() && a[st.back()] < a[i]) {
      st.pop_back();
    }
    if (st.size()) {
      cands.push_back({i, st.back()});
    }
    st.push_back(i);
  }
  cin >> q;
  vector<array<int, 3>> Queries;
  for (int i = 1; i <= q; ++i) {
    int l, r; cin >> l >> r;
    Queries.push_back({l, r, i});
  }
  sort(cands.rbegin(), cands.rend());
  sort(Queries.rbegin(), Queries.rend());
  int j = 0;
  for (auto [l, r, id] : Queries) {
    while (j < cands.size() && cands[j][0] >= l) {
      int c = 2 * cands[j][1] - cands[j][0];
      if (c <= n) {
        upd(c, n, a[cands[j][0]] + a[cands[j][1]]);
      }
      ++j;
    }
    res[id] = qry(l, r);
  }
  for (int i = 1; i <= q; ++i) {
    cout << res[i] << "\n";
  }
  return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:108:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     while (j < cands.size() && cands[j][0] >= l) {
      |            ~~^~~~~~~~~~~~~~

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