Submission #199387

#	Time	Username	Problem	Language	Result	Execution time	Memory
199387		EntityIT	Triple Jump (JOI19_jumps)	C++14	100 / 100	1221 ms	99196 KiB

jumps

/*
  Just consider the pair(a, b) such that with every a < k < b, a[a] > a[k] and a[b] > a[k]
  The number of these pairs is just O(n): the proof can be expressed by the code finding these pairs
  The rest is quite easy
*/
#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

const int inf = 1e9;
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }

int n;
vector<int> a;

struct Node {
  int mxA, mxOth, mx;
  Node(int _mxA = 0, int _mxOth = 0, int _mx = 0) : mxA(_mxA), mxOth(_mxOth), mx(_mx) {}
};

struct It {
  vector<Node> node;
  It(int nNode) { node.assign(nNode, 0); }

  void build(int i = 1, int Left = 0, int Right = n - 1) {
    if (Left == Right) {
      node[i] = Node(a[Left], -inf, -inf);
      return ;
    }
    int Mid = (Left + Right) >> 1;
    build(i << 1, Left, Mid);
    build(i << 1 | 1, Mid + 1, Right);
    node[i].mxA = max(node[i << 1].mxA, node[i << 1 | 1].mxA);
  }

  void upd(int l, int r, int val, int i = 1, int Left = 0, int Right = n - 1) {
    if (i != 1) {
      asMx(node[i].mxOth, node[i >> 1].mxOth);
      asMx(node[i].mx, node[i].mxOth + node[i].mxA);
    }

    if (Right < l || r < Left) return ;
    if (l <= Left && Right <= r) {
      asMx(node[i].mxOth, val); asMx(node[i].mx, node[i].mxOth + node[i].mxA);
      return ;
    }

    int Mid = (Left + Right) >> 1;
    upd(l, r, val, i << 1, Left, Mid);
    upd(l, r, val, i << 1 | 1, Mid + 1, Right);
    node[i].mx = max(node[i << 1].mx, node[i << 1 | 1].mx);
  }

  int getMx(int l, int r, int i = 1, int Left = 0, int Right = n - 1) {
    if (i != 1) {
      asMx(node[i].mxOth, node[i >> 1].mxOth);
      asMx(node[i].mx, node[i].mxOth + node[i].mxA);
    }

    if (Right < l || r < Left) return -inf;
    if (l <= Left && Right <= r) return node[i].mx;

    int Mid = (Left + Right) >> 1;
    return max(getMx(l, r, i << 1, Left, Mid), getMx(l, r, i << 1 | 1, Mid + 1, Right) );
  }
};

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafCLover

  cin >> n;
  a.assign(n, 0);
  for (int i = 0; i < n; ++i) cin >> a[i];

  vector<vector<int> > paired(n);
  stack<int> st;
  for (int i = 0; i < n; ++i) {
    while (sz(st) && a[st.top()] <= a[i]) {
      paired[st.top()].emplace_back(i);
      st.pop();
    }
    if (sz(st) ) paired[st.top()].emplace_back(i);

    st.emplace(i);
  }

  int q; cin >> q;
  vector<vector<pair<int, int> > > que(n);
  for (int i = 0; i < q; ++i) {
    int l, r; cin >> l >> r; --l; --r;
    que[l].emplace_back(r, i);
  }

  vector<int> ans(q);
  It it( (n + 5) << 2);
  it.build();
  for (int i = n - 1; i >= 0; --i) {
    for (int j : paired[i]) if ( (j << 1) - i <= n - 1) it.upd( (j << 1) - i, n - 1, a[i] + a[j]);

    for (auto query : que[i]) ans[query.second] = it.getMx(i, query.first);
  }

  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