Submission #570882

#	Time	Username	Problem	Language	Result	Execution time	Memory
570882		OttoTheDino	Triple Jump (JOI19_jumps)	C++17	100 / 100	1041 ms	66864 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

#define rep(i,s,e)                  for (int i = s; i <= e; ++i)
#define rrep(i,s,e)                 for (int i = s; i >= e; --i)
#define pb                          push_back
#define pf                          push_front
#define fi                          first
#define se                          second
#define all(a)                      a.begin(), a.end()
#define len(a)                      (int)a.size()
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;

const int mx = 5e5;
int seg[4*mx+5], lazy[4*mx+5], a[mx+1], b[mx+2];
set<int> st;

void upd (int l, int r, int bl, int br, int val, int id) {
    if (l==bl && r==br) {
        seg[id] += val;
        lazy[id] += val;
        return;
    }
    int mid = (bl+br)/2;
    if (r<=mid) upd (l, r, bl, mid, val, 2*id);
    else if (l>mid) upd (l, r, mid+1, br, val, 2*id+1);
    else {
        upd (l, mid, bl, mid, val, 2*id);
        upd (mid+1, r, mid+1, br, val, 2*id+1);
    }
    seg[id] = max(seg[2*id], seg[2*id+1])+lazy[id];
}

int qry (int l, int r, int bl, int br, int id) {
    if (l==bl && r==br) return seg[id];

    int mid = (bl+br)/2;
    if (r<=mid) return lazy[id] + qry (l, r, bl, mid, 2*id);
    if (l>mid) return lazy[id] + qry (l, r, mid+1, br, 2*id+1);
    return lazy[id] + max( qry(l, mid, bl, mid, 2*id), qry(mid+1, r, mid+1, br, 2*id+1));
}

void adij (int i, int j) {
    int x = 2*j-i;
    if (x>=*st.rbegin()) return;
    auto it = st.upper_bound(x);
    if (it!=st.begin()) {
        if (a[i]+a[j] > b[*prev(it)]) {
            upd (x, *it-1, 1, mx, a[i]+a[j] - b[*prev(it)], 1);
            b[x] = a[i]+a[j];
            st.insert(x);
        }
    }
    else {
        upd (x, *it-1, 1, mx, a[i]+a[j], 1);
        b[x] = a[i]+a[j];
        st.insert(x);
    }
    while (a[i]+a[j] > b[*it]) {
        upd (*it, *next(it)-1, 1, mx, a[i]+a[j]-b[*it], 1);
        it = st.erase(it);
    }
}

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

    int n, q; cin >> n;
    st.insert(n+1);
    b[n+1] = 1e9;
    vii rs[n+1];
    rep (i,1,n) cin >> a[i];
    cin >> q;
    int ans[q+1] = {};
    rep (i,1,q) {
        int l, r; cin >> l >> r;
        rs[l].pb({r,i});
    }
    stack<int> js;
    rrep (i,n,1) {
        upd (i, i, 1, mx, a[i], 1);
        while ( len(js) && a[js.top()] < a[i]) {
            adij(i, js.top());
            js.pop();
        } 
        if (len(js)) adij(i, js.top());
        js.push(i);
        for (ii ri : rs[i]) ans[ri.se] = qry (i+2, ri.fi, 1, mx, 1);
    }
    rep (i,1,q) cout << ans[i] << "\n";
    return 0;
}

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