Submission #979835

#	Time	Username	Problem	Language	Result	Execution time	Memory
979835		peterandvoi	Triple Jump (JOI19_jumps)	C++17	100 / 100	637 ms	87896 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int q;
    cin >> q;
    vector<vector<pair<int, int>>> qry(n);
    vector<vector<int>> g(n);
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        l--, r--;
        qry[l].emplace_back(r, i);
    }
    vector<int> st;
    for (int i = 0; i < n; ++i) {
        while (st.size() && a[st.back()] < a[i]) {
            st.pop_back();
        }
        if (st.size()) {
            g[st.back()].emplace_back(i);
        }
        st.emplace_back(i);
    }
    while (st.size()) {
        st.pop_back();
    }
    for (int i = n - 1; ~i; --i) {
        while (st.size() && a[st.back()] <= a[i]) {
            st.pop_back();
        }
        if (st.size()) {
            g[i].emplace_back(st.back());
        }
        st.emplace_back(i);
    }
    const int INF = int(1e9);
    vector<int> s(4 << __lg(n), -INF);
    auto lz = s;
    auto mx = s;
    auto app = [&](int id, int x) {
        lz[id] = max(lz[id], x);
        s[id] = max(s[id], x + mx[id]);
    };
    auto psh = [&](int id) {
        app(id * 2, lz[id]);
        app(id * 2 + 1, lz[id]);
        lz[id] = -INF;
    };
    auto updP = [&](int i) {
        int id = 1, l = 0, r = n - 1;
        while (l ^ r) {
            int md = (l + r) / 2;
            if (lz[id] != -INF) {
                psh(id);
            }
            id *= 2;
            if (i <= md) {
                r = md;
            } else {
                l = md + 1;
                id += 1;
            }
        }
        mx[id] = a[i];
        while (id > 1) {
            id /= 2;
            mx[id] = max(mx[id * 2], mx[id * 2 + 1]);
        }
    };
    auto upd = [&](int i, int x) {
        int id = 1, l = 0, r = n - 1;
        while (l ^ r) {
            int md = (l + r) / 2;
            if (lz[id] != -INF) {
                psh(id);
            }
            id *= 2;
            if (i - 1 <= md) {
                app(id + 1, x);
                r = md;
            } else {
                id += 1;
                l = md + 1;
            }
        }
        while (id > 1) {
            id /= 2;
            s[id] = max(s[id * 2], s[id * 2 + 1]);
        }
    };
    auto get = [&](int i) {
        int id = 1, l = 0, r = n - 1;
        int res = -INF;
        while (l ^ r) {
            int md = (l + r) / 2;
            if (lz[id] != -INF) {
                psh(id);
            }
            id *= 2;
            if (i <= md) {
                r = md;
            } else {
                res = max(res, s[id]);
                l = md + 1;
                id += 1;
            }
        }
        return max(res, s[id]);
    };
    vector<int> res(q);
    for (int l = n - 1; ~l; --l) {
        updP(l);
        for (int r : g[l]) {
            upd(2 * r - l, a[l] + a[r]);
        }
        for (auto [r, id] : qry[l]) {
            res[id] = get(r);
        }
    }
    for (int i = 0; i < q; ++i) {
        cout << res[i] << "\n";
    }
}

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