Submission #139365

#	Time	Username	Problem	Language	Result	Execution time	Memory
139365		IOrtroiii	Triple Jump (JOI19_jumps)	C++14	100 / 100	1447 ms	136184 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int N = 500500;
const ll inf = 1e18;

struct State {
   ll pref, suf, ans;
   State() : pref(-inf), suf(-inf), ans(-inf) {}
   friend State operator + (const State &l, const State &r) {
      State ans;
      ans.pref = max(l.pref, r.pref);
      ans.suf = max(l.suf, r.suf);
      ans.ans = max({l.ans, r.ans, l.pref + r.suf});
      return ans;
   }
};

ll a[N];
State t[N << 2];
ll ans[N];
vector<pair<int, ll>> es[N];
vector<pair<int, int>> qs[N];

void build(int v, int l, int r) {
   if (l == r) {
      t[v].suf = a[l];
      return;
   }
   int md = (l + r) >> 1;
   build(v << 1, l, md);
   build(v << 1 | 1, md + 1, r);
   t[v] = t[v << 1] + t[v << 1 | 1];
}

void mdf(int v, int l, int r, int p, ll val) {
   if (l == r) {
      t[v].pref = max(t[v].pref, val);
      return;
   }
   int md = (l + r) >> 1;
   if (p <= md) {
      mdf(v << 1, l, md, p, val);
   } else {
      mdf(v << 1 | 1, md + 1, r, p, val);
   }
   t[v] = t[v << 1] + t[v << 1 | 1];
}

State get(int v, int l, int r, int L, int R) {
   if (L > r || R < l) return State();
   if (L <= l && r <= R) {
      return t[v];
   }
   int md = (l + r) >> 1;
   return get(v << 1, l, md, L, R) + get(v << 1 | 1, md + 1, r, L, R);
}

int main() {
   ios_base::sync_with_stdio(false);
   int n;
   cin >> n;
   vector<int> st;
   for (int i = 1; i <= n; ++i) {
      cin >> a[i];
      while (!st.empty()) {
         int go = 2 * i - st.back() - 1;
         if (go < n) es[st.back()].emplace_back(a[i] + a[st.back()], go);
         if (a[i] < a[st.back()]) {
            break;
         } else {
            st.pop_back();
         }
      }
      st.emplace_back(i);
   }
   int q;
   cin >> q;
   for (int i = 1; i <= q; ++i) {
      int l, r;
      cin >> l >> r;
      qs[l].emplace_back(r, i);
   }
   build(1, 1, n);
   for (int i = n; i > 0; --i) {
      for (auto e : es[i]) {
         mdf(1, 1, n, e.second, e.first);
      }
      for (auto q : qs[i]) {
         ans[q.second] = get(1, 1, n, i, q.first).ans;
      }
   }
   for (int i = 1; i <= q; ++i) {
      cout << ans[i] << "\n";
   }
}

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