Submission #146067

#	Time	Username	Problem	Language	Result	Execution time	Memory
146067		fedoseevtimofey	Triple Jump (JOI19_jumps)	C++14	100 / 100	1435 ms	114856 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int Inf = 2e9;

struct Node {
    int sum, val, mx;
    Node() {
        sum = mx = -Inf;
        val = 0;
    }
    Node operator +(const Node &other) const {
        Node res;
        res.sum = max(sum, other.sum);
        res.val = max(val, other.val);
        res.mx = max(mx, other.mx);
        res.mx = max(res.mx, sum + other.val);
        return res;
    }
};

const int N = 5e5 + 7;
Node t[4 * N];

void build(int l, int r, int v, vector <int> &a) {
    if (l == r) {
        t[v].val = a[l];
    } else {
        int m = (l + r) >> 1;
        build(l, m, 2 * v + 1, a);
        build(m + 1, r, 2 * v + 2, a);
        t[v] = t[2 * v + 1] + t[2 * v + 2];
    }
}

void modify(int ind, int sm, int l, int r, int v) {
    if (l == r) {
        t[v].sum = max(t[v].sum, sm);
        t[v].mx = t[v].val + t[v].sum;
    } else {
        int m = (l + r) >> 1;
        if (ind <= m) modify(ind, sm, l, m, 2 * v + 1);
        else modify(ind, sm, m + 1, r, 2 * v + 2);
        t[v] = t[2 * v + 1] + t[2 * v + 2];
    }
}

Node get(int ql, int qr, int l, int r, int v) {
    if (qr < l || r < ql) return Node();
    if (ql <= l && r <= qr) return t[v];
    int m = (l + r) >> 1;
    return get(ql, qr, l, m, 2 * v + 1) + get(ql, qr, m + 1, r, 2 * v + 2);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int n;
    cin >> n;
    vector <int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }
    vector <int> L(n, -1), R(n, n);
    vector <pair <int, int>> st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && st.back().first < A[i]) st.pop_back();
        if (!st.empty()) L[i] = st.back().second;
        st.push_back({A[i], i});
    }
    st.clear();
    for (int i = n - 1; i >= 0; --i) {
        while (!st.empty() && st.back().first <= A[i]) st.pop_back();
        if (!st.empty()) R[i] = st.back().second;
        st.push_back({A[i], i});
    }
    vector <pair <int, int>> intr;
    for (int i = 0; i < n; ++i) {
        int j = L[i];
        if (j != -1) {
            intr.push_back({j, i});
        }
        j = R[i];
        if (j != n) {
            intr.push_back({i, j});
        }
    }
    sort(intr.begin(), intr.end());
    intr.resize(unique(intr.begin(), intr.end()) - intr.begin());
    build(0, n - 1, 0, A);
    vector <vector <int>> who(n);
    for (auto p : intr) {
        who[p.first].push_back(p.second);
    }
    int q;
    cin >> q;
    vector <int> ql(q), qr(q);
    vector <int> ans(q);
    vector <vector <int>> qrs(n);
    for (int i = 0; i < q; ++i) {
        cin >> ql[i] >> qr[i];
        --ql[i], --qr[i];
        qrs[ql[i]].push_back(i);
    }
    for (int i = n - 1; i >= 0; --i) {
        for (int j : who[i]) {
            if (j + j - i < n) {
                modify(j + j - i, A[i] + A[j], 0, n - 1, 0);
            }
        }
        for (int id : qrs[i]) {
            ans[id] = get(ql[id], qr[id], 0, n - 1, 0).mx;
        }
    }
    for (int i = 0; i < q; ++i) cout << ans[i] << '\n';
}   

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